Graph homomorphism reconfiguration and frozen H-colorings

For a fixed graph H, the reconfiguration problem for H-colorings (ie, homomorphisms to H) asks: given a graph G and two H-colorings (Formula presented.) and (Formula presented.) of G, does there exist a sequence (Formula presented.) of H-colorings such that (Formula presented.), (Formula presented.), and (Formula presented.) for every (Formula presented.) and (Formula presented.) ? If the graph G is loop-free, then this is the equivalent to asking whether it possible to transform (Formula presented.) into (Formula presented.) by changing the color of one vertex at a time such that all intermediate mappings are H-colorings. In the affirmative, we say that (Formula presented.) reconfigures to (Formula presented.). Currently, the complexity of deciding whether an H-coloring (Formula presented.) reconfigures to an H-coloring (Formula presented.) is only known when H is a clique, a circular clique, a (Formula presented.) -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 (Formula presented.) such that (Formula presented.) does not reconfigure to any H-coloring (Formula presented.) such that (Formula presented.). 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.