Abstract:

The ${\tt Hom}$--complexes were introduced by Lov\'asz to study topological obstructions to graph colorings. It was conjectured by Babson and Kozlov, and proved by \v{C}uki\'c and Kozlov, that ${\tt Hom}(G,K_n)$ is $(n-d-2)$--connected, where $d$ is the maximal degree of a vertex of $G$.

A greedy algorithm colors a graph by successively choosing maximal independent sets. Let $\dot{\chi}(G)$ be the maximal number of colors it uses for the graph $G$. Then $\chi(G)\leq \dot{\chi}(G)\leq d+1$.

We give a short proof of that ${\tt Hom}(G,K_n)$ is $(n-\dot{\chi}(G)-1)$--connected.