A topological lower bound for the chromatic number of a special family of graphs

Abstract

For studying topological obstructions to graph colorings, Hom-complexes were introduced by Lovász. A graph $T$ is called a test graph if for every graph $H$, the $k$-connectedness of $|Hom(T,H)|$ implies $\chi (H)\ge k+1+\chi (T)$. The proof of the famous Kneser conjecture is based on the fact that ${\mathcal{K}}_2$, the complete graph on $2$ vertices, is a test graph. This result was extended to all complete graphs by Babson and Kozlov. Their proof is based on generalized nerve lemma and discrete Morse theory. In this paper, we propose a new topological lower bound for the chromatic number of a special family of graphs. As an application of this bound, we give a new proof of the well-known fact that complete graphs and even cycles are test graphs.