Characterizing circular colouring mixing for pq<4 \frac{p}{q}\lt 4

DOI10.1002/JGT.22870MaRDI QIDQ6093150zbMATH OpenOpenAlexFDO

Authors Richard C. Brewster, Benjamin Moore

Publication date 6 October 2023

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

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

zbMATH Keywords

colouringhomomorphismmixingreconfiguration

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: Given a graph $G$, the $k$-mixing problem asks: Can one obtain all $k$-colourings of $G$, starting from one $k$-colouring $f$, by changing the colour of only one vertex at a time, while at each step maintaining a $k$-colouring? More generally, for a graph $H$, the $H$-mixing problem asks: Can one obtain all homomorphisms $GoH$, starting from one homomorphism $f$, by changing the image of only one vertex at a time, while at each step maintaining a homomorphism $GoH$? This paper focuses on a generalization of $k$-colourings, namely $(p,q)$-circular colourings. We show that when $2<fracpq<4$, a graph $G$ is $(p,q)$-mixing if and only if for any $(p,q)$-colouring $f$ of $G$, and any cycle $C$ of $G$, the wind of the cycle under the colouring equals a particular value (which intuitively corresponds to having no wind). As a consequence we show that $(p,q)$-mixing is closed under a restricted homomorphism called a fold. Using this, we deduce that $(2k+1,k)$-mixing is co-NP-complete for all $kinmathbbN$, and by similar ideas we show that if the circular chromatic number of a connected graph $G$ is $frac2k+1k$, then $G$ folds to $C_{2k+1}$. We use the characterization to settle a conjecture of Brewster and Noel, specifically that the circular mixing number of bipartite graphs is $2$. Lastly, we give a polynomial time algorithm for $(p,q)$-mixing in planar graphs when $3leqfracpq<4$.

Recommendations

• Mixing homomorphisms, recolorings, and extending circular precolorings
• A dichotomy theorem for circular colouring reconfiguration
• Circular mixed hypergraphs. I: Colorability and unique colorability
• Circular and uniquely colorable mixed hypergraphs
• On two questions about circular choosability

Cites work

• A dichotomy theorem for circular colouring reconfiguration
• A note on the star chromatic number
• A Thomassen-type method for planar graph recoloring
• Circular chromatic number: A survey
• Circular colouring and graph homomorphism
• Computational complexity of compaction to irreflexive cycles
• Distributed recoloring
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Graph homomorphism reconfiguration and frozen \(H\)-colorings
• Graph theory
• Homomorphism reconfiguration via homotopy
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3666852 (Why is no real title available?)
• scientific article; zbMATH DE number 1054727 (Why is no real title available?)
• scientific article; zbMATH DE number 1151810 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• Introduction to reconfiguration
• Mixing 3-colourings in bipartite graphs
• Mixing homomorphisms, recolorings, and extending circular precolorings
• On the complexity of reconfiguration problems
• Recolouring reflexive digraphs
• Reconfiguration in bounded bandwidth and tree-depth
• Reconfiguring graph homomorphisms on the sphere
• The coloring reconfiguration problem on specific graph classes
• The complexity of change

Cited in

(2)

• Mixing homomorphisms, recolorings, and extending circular precolorings
• Mixing is hard for triangle-free reflexive graphs

This page was built for publication: Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$

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