Graph homomorphism reconfiguration and frozen H‐colorings. Issue 3 (9th December 2019)

• Record Type: Journal Article
• Authors: Brewster, Richard C.; Lee, Jae‐Baek; Moore, Benjamin; Noel, Jonathan A.; Siggers, Mark
• Is Part Of: Journal of graph theory. Volume 94:Issue 3(2020)
• Page Start: 398
• Page End: 420
• Publication Date: 2019-12-09
• Subjects: complexity -- graph homomorphism -- recoloring -- reconfiguration; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22530
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: For a fixed graph H, the reconfiguration problem for H ‐colorings (ie, homomorphisms to H ) asks: given a graph G and two H ‐colorings φ and ψ of G, does there exist a sequence f 0, …, f m of H ‐colorings such that f 0 = φ, f m = ψ, and f i ( u ) f i + 1 ( v ) ∈ E ( H ) for every 0 ≤ i < m and u v ∈ E ( G ) ? If the graph G is loop‐free, then this is the equivalent to asking whether it possible to transform φ into ψ by changing the color of one vertex at a time such that all intermediate mappings are H ‐colorings. In the affirmative, we say that φ reconfigures to ψ . Currently, the complexity of deciding whether an H ‐coloring φ reconfigures to an H ‐coloring ψ is only known when H is a clique, a circular clique, a C 4 ‐free graph, or in a few other cases which are easily derived from these. We show that this problem is PSPACE‐complete when H is an odd wheel. An important notion in the study of reconfiguration problems for H ‐colorings is that of a frozen H‐coloring ; that is, an H ‐coloring φ such that φ does not reconfigure to any H ‐coloring ψ such that ψ ≠ φ . We obtain an explicit dichotomy theorem for the problem of deciding whether a given graph G admits a frozen H ‐coloring. The hardness proof involves a reduction from a constraint satisfaction problem which is shown to be nondeterministic polynomial time NP‐complete by establishing the nonexistence of a certain type of polymorphism.