A short proof of a conjecture on the connectivity of graph coloring complexes

摘要

The Hom-complexes were introduced by Lovasz to study topological obstructions to graph colorings. It was conjectured by Babson and Kozlov, and proved by Cukic and Kozlov, that Hom(G, K-n) is (n - d - 2)-connected, where d is the maximal degree of a vertex of G, and n the number of colors. We give a short proof of the conjecture.