Homotopy types of Hom complexes of graph homomorphisms whose codomains are cycles

2024/08/09 by Fujii, Soichiro, Iwamasa, Yuni, Kimura, Kei +2 · 1 citation
#05C15 (Primary) 55P15 (Secondary) #55U05 #Algebraic Topology (math.AT) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2408.04802

Abstract

For simple graphs G and H, the Hom complex Hom(G,H) is a polyhedral complex whose vertices are the graph homomorphisms G→ H and whose edges connect the pairs of homomorphisms which differ in a single vertex of G. Hom complexes play an important role in an algebro-topological approach to the graph coloring problem. It is known that Hom(G,H) is homotopy equivalent to a disjoint union of points and circles when both G and H are cycles. We generalize this known result by showing that the same holds whenever G is connected and H is a cycle. To this end, we explicitly construct the universal cover of each connected component of Hom(G,H) and prove that it is contractible. Additionally, we provide a simple criterion to determine whether the connected component containing a given homomorphism is homotopy equivalent to a point or circle.

Cited by

• Towards an algebraic approach to the reconfiguration CSP

Related

• Hom complexes of graphs whose codomains are square-free
• Homotopy types of Hom complexes of graph homomorphisms whose codomains are square-free
• The homotopy type of complexes of graph homomorphisms between cycles
• Simple S_r-homotopy types of Hom complexes and box complexes associated to r-graphs
• Hom complexes and homotopy theory in the category of graphs