Graph homomorphism reconfiguration and frozen H-colorings. Brewster, R. C., Lee, J., Moore, B., Noel, J. A., & Siggers, M. Journal of Graph Theory, December, 2019.
Graph homomorphism reconfiguration and frozen H-colorings [link]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
About
Documentation
Keywords
Search
Users
Terms and Conditions of Use
Privacy Policy
Sitemap
© BibBase.org 2021