Connectedness of certain graph coloring complexes (Q6581825)

Let \(\mathrm{Hom}(G,H)\) denote the set of homomorphisms from the graph \(G\) to the graph \(H\). In the present paper, the authors study the connectedness of the simplicial complex derived from \(\mathrm{Hom}(G,H)\) in the case when \(H\) is the bipartite graph \(K_2\times K_n\) where \(K_n\) is the complete graph on \(n\) vertices. \textit{G. Malen} [Discrete Math. 341, No. 9, 2567--2574 (2018; Zbl 1392.05056)] showed that \(\mathrm{Hom}(G, K_n)\) is at least \((n - D - 2)\)-connected, where \(D=\max \delta (H)_{H\subseteq G}\), \(\delta (H)\) denotes the minimal degree of a vertex in a graph \(H\) and the maximum is taken over all induced subgraphs \(H\) of \(G\). Therefore, in this relation it was natural to ask for which \(G\) the complex \(\mathrm{Hom}(G, K_n)\) is exactly \((n - D - 2)\)-connected. The main result of the authors is Theorem 1.1 which provides the exact formula for the topological connectivity of the complex \(\mathrm{Hom}(G, K_m)\) in the case of the bipartite graphs \(G=K_2\times K_n\). To prove this theorem, the authors use the facts that \(\mathrm{Hom}(K_2\times K_n, K_m)\simeq\mathrm{Hom}(K_2, K_m^{K_n})\) where \(K_m^{K_n}\) is the exponential graph and the connectedness \(\mathrm{conn}(\mathrm{Hom} (K_2, K_m^{K_n}))\) of the complex \(\mathrm{Hom} (K_2,K_m^{K_n})\) is the same as the connectedness \(\mathrm{conn}(\mathcal{N} (K_m^{K_n}))\) of the neighborhood complex \(\mathcal{N} (K_m^{K_n})\). The main tool in the proof of this result is discrete Morse theory.