Connectedness of Certain Graph Coloring Complexes

Nandini Nilakantan; Samir Shukla

paper

Connectedness of Certain Graph Coloring Complexes

arXiv:1702.03527

Abstract

In this article, we consider the bipartite graphs $K_{2} \times K_{n}$ . We prove that the connectedness of the complex $Hom (K_{2} \times K_{n}, K_{m})$ is $m - n - 1$ if $m \geq n$ and $m - 3$ in the other cases. Therefore, we show that for this class of graphs, $Hom (G, K_{m})$ is exactly $m - d - 2$ connected, $m \geq n$ , where $d$ is the maximal degree of the graph $G$ .

19 pages