A short proof of a conjecture on the connectivity of graph coloring complexes
Alexander Engström · Proceedings of the American Mathematical Society · 2006
The H o m \mathtt {Hom} –complexes were introduced by Lovász to study topological obstructions to graph colorings. It was conjectured by Babson and Kozlov, and proved by Čukić and Kozlov, that H o m ( G , K n ) \mathtt {Hom}(G,K_n) is ( n − d − 2 ) (n-d-2) –connected, where d d is the maximal degree of a vertex of G G , and n n the number of colors. We give a short proof of the conjecture.