Proof of the Lovász conjecture
Eric K. Babson, Dmitry N. Kozlov · Annals of Mathematics · 2007
To any two graphs G and H one can associate a cell complex 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 thatwhere r, k ∈ Z, r ≥ 1, k ≥ -1, and C 2r+1 denotes the cycle with 2r +1 vertices.The proof requires analysis of the complexes Hom (C 2r+1 , K n ).For even n, the obstructions to graph colorings are provided by the presence of torsion in H * (Hom (C 2r+1 , K n ); Z).For odd n, the obstructions are expressed as vanishing of certain powers of Stiefel-Whitney characteristic classes of Hom (C 2r+1 , K n ), where the latter are viewed as Z 2 -spaces with the involution induced by the reflection of C 2r+1 .