The homotopy type of complexes of graph homomorphisms between cycles (Q2505230)

For a graph \(G\), we denote by \(V(G)\) the set of its vertices, and for two graphs \(G\) and \(H\), a graph homomorphism \(G\to H\) means a map \(\phi :V(G)\to V(H)\) such that if \(x,y\in V(G)\) are connected by an edge then \(\phi (x)\) and \(\phi (y)\) are also connected by an edge. Let \(C_k\) be the cyclic graph with \(k\) vertices and let \(L_n\) denote a tree with \(n\) vertices and no branching point. In this paper, the authors study the homotopy type of \(\text{Hom} (C_m,C_n)\), where \(\text{Hom}(C_m,C_n)\) denotes the set of all graph homomorphisms from \(C_m\) to \(C_n\). In particular, they enumerate connected components of \(\text{Hom} (C_m,C_n)\) and show that each such component is either homeomorphic to a point or homotopy equivalent to \(S^1\). Furthermore, they prove that \(\text{Hom}(C_m,L_n)\) is either empty or is homotopy equivalent to the union of two points. To prove these results, they use discrete Morse theory with the classical homotopy gluing construction (cf. [\textit{A. Hatcher}, Algebraic Topology, (Cambridge): Cambridge University Press, (2002; Zbl 1044.55001)]).