Paper doi abstract bibtex

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 f0,…,fm of H-colorings such that f0=φ, fm=ψ, and fi(u)fi+1(v)∈E(H) for every 0≤i\textlessm and uv∈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 C4-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.

@article{brewster_graph_2019, title = {Graph homomorphism reconfiguration and frozen {H}-colorings}, volume = {n/a}, copyright = {© 2019 Wiley Periodicals, Inc.}, issn = {1097-0118}, url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22530}, doi = {10.1002/jgt.22530}, 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 f0,…,fm of H-colorings such that f0=φ, fm=ψ, and fi(u)fi+1(v)∈E(H) for every 0≤i{\textless}m and uv∈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 C4-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.}, language = {en}, number = {n/a}, urldate = {2020-01-22}, journal = {Journal of Graph Theory}, author = {Brewster, Richard C. and Lee, Jae-Baek and Moore, Benjamin and Noel, Jonathan A. and Siggers, Mark}, month = dec, year = {2019}, keywords = {complexity, graph homomorphism, recoloring, reconfiguration} }

Downloads: 0