Hom complexes of graphs whose codomains are square-free

2024/12/26 by Matsushita, Takahiro · 3 citations
#Algebraic Topology (math.AT) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2412.19144

Abstract

The Hom complex 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. %Recently, Soichiro Fujii, Yuni Iwamasa, Kei Kimura, Yuta Nozaki and Akira Suzuki showed that if G is a connected graph and H is a cycle graph then every connected component of Hom(G, H) is contractible or homotopy equivalent to a circle. 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 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 Hom(G,H) and realizable walks studied in the homomorphism reconfiguration problem.

Cited by

• Towards an algebraic approach to the reconfiguration CSP
• Closed neighborhood complexes of graphs
• Higher-dimensional generalization of Youngs' theorem and circular colorings

Related

• Homotopy types of Hom complexes of graph homomorphisms whose codomains are cycles
• Homotopy types of Hom complexes of graph homomorphisms whose codomains are square-free
• Hom complexes of graphs of diameter 1
• Simple S_r-homotopy types of Hom complexes and box complexes associated to r-graphs
• The universality of Hom complexes