Hom complexes of graphs whose codomains are square-free
Abstract
The Hom complex $\mathrm{Hom}(G, H)$ of graphs is a simplicial complex associated to a pair of graphs $G$ and $H$, and its homotopy type is of interest in the graph coloring problem and the homomorphism reconfiguration problem. In this paper, we show that if $G$ is a connected graph and $H$ is a square-free connected graph, then every connected component of $\mathrm{Hom}(G, H)$ is homotopy equivalent to a point, a circle, $H$ or a connected double cover over $H$. We also obtain a certain relation between the fundamental group of $\mathrm{Hom}(G,H)$ and realizable walks studied in the homomorphism reconfiguration problem.
Fields of Study & Subjects
Topological and Geometric Data Analysis
Graph theory and applications
Axial and Atropisomeric Chirality Synthesis
Publication details
- Journal / source
- Journal of Combinatorial Theory Series B
- Publisher
- Elsevier BV
- Volume
- 178
- Pages
- 267–293
- Publication date
- 2 February 2026
- Language
- EN