Graph homomorphism reconfiguration and frozen H‐colorings
Richard C. Brewster, Jae-baek Lee, Benjamin R. Moore, Jonathan A. Noel, Mark Siggers · Journal of Graph Theory · 2019
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 of H‐colorings such that , , and for every and ? 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 ‐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.