Proof of the Lovász conjecture


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}$.


Eric Babson

Department of Mathematics, University of Washington, Seattle, WA 98195, United States

Dmitry N. Kozlov

Departement Mathematik, Eidgenössische Technische Hochschule, 8092 Zürich, Switzerland