Abstract
To any two graphs $G$ and $H$ one can associate a cell complex ${\tt Hom}(G,H)$ by taking all graph multihomomorphisms from $G$ to $H$ as cells.
In this paper we prove the Lovász conjecture which states that
if ${\tt Hom}(C_{2r+1},G)$ is $k$-connected, then $\chi(G)\geq k+4,$
where $r,k\in\mathbb{Z}$, $r\geq 1$, $k\geq -1$, and $C_{2r+1}$ denotes the cycle with $2r+1$ vertices.
The proof requires analysis of the complexes ${\tt Hom}(C_{2r+1},K_n)$. For even $n$, the obstructions to graph colorings are provided by the presence of torsion in $H^*({\tt Hom}(C_{2r+1},K_n);\mathbb{Z})$. For odd $n$, the obstructions are expressed as vanishing of certain powers of Stiefel-Whitney characteristic classes of ${\tt Hom}(C_{2r+1},K_n)$, where the latter are viewed as $\mathbb{Z}_2$-spaces with the involution induced by the reflection of $C_{2r+1}$.
Full Article