Graph homomorphism reconfiguration and frozen H-colorings

DOI10.1002/JGT.22530MaRDI QIDQ5066895zbMATH OpenOpenAlexWikidataFDO

Authors Richard C. Brewster, J. B. Lee, Benjamin Moore, Jonathan A. Noel, Mark Siggers

Publication date 31 March 2022

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.00200

zbMATH Keywords

complexitygraph homomorphismrecoloringreconfiguration

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: For a fixed graph $H$, the reconfiguration problem for $H$-colourings (i.e. homomorphisms to $H$) asks: given a graph $G$ and two $H$-colourings $varphi$ and $psi$ of $G$, does there exist a sequence $f_0,dots,f_m$ of $H$-colourings such that $f_0=varphi$, $f_m=psi$ and $f_i(u)f_{i+1}(v)inE(H)$ for every $0leqi<m$ and $uvinE(G)$? If the graph $G$ is loop-free, then this is the equivalent to asking whether it possible to transform $varphi$ into $psi$ by changing the colour of one vertex at a time such that all intermediate mappings are $H$-colourings. In the affirmative, we say that $varphi$ reconfigures to $psi$. Currently, the complexity of deciding whether an $H$-colouring $varphi$ reconfigures to an $H$-colouring $psi$ 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$-colourings is that of a frozen $H$-colouring; i.e. an $H$-colouring $varphi$ such that $varphi$ does not reconfigure to any $H$-colouring $psi$ such that $psieqvarphi$. We obtain an explicit dichotomy theorem for the problem of deciding whether a given graph $G$ admits a frozen $H$-colouring. The hardness proof involves a reduction from a CSP problem which is shown to be NP-complete by establishing the non-existence of a certain type of polymorphism.

Recommendations

• Reconfiguring graph homomorphisms on the sphere
• Homomorphism reconfiguration via homotopy
• Homomorphism reconfiguration via homotopy
• A dichotomy theorem for circular colouring reconfiguration
• Complexity of coloring reconfiguration under recolorability constraints

Cited in

(8)

• Reconfiguring graph homomorphisms on the sphere
• Introduction to reconfiguration
• Recolouring homomorphisms to triangle-free reflexive graphs
• Homomorphism reconfiguration via homotopy
• Homomorphism reconfiguration via homotopy
• Hedetniemi's conjecture and strongly multiplicative graphs
• Frozen development in graph coloring
• Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$

This page was built for publication: Graph homomorphism reconfiguration and frozen \(H\)-colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066895)