Graph homomorphism reconfiguration and frozen H‐colorings. Issue 3 (9th December 2019) - Brewster, Richard C.; Lee, Jae‐Baek; Moore, Benjamin; Noel, Jonathan A.; Siggers, Mark
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.