Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$. Issue 2 (5th August 2022)

• Record Type: Journal Article
• Authors: Brewster, Richard C.; Moore, Benjamin
• Is Part Of: Journal of graph theory. Volume 102:Issue 2(2023)
• Page Start: 271
• Page End: 294
• Publication Date: 2022-08-05
• Subjects: colouring -- graph theory -- homomorphism -- mixing -- reconfiguration; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22870
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: Given a graph G $G$, the k $k$ ‐mixing problem asks: Starting with a k $k$ ‐colouring of G $G$, can one obtain all k $k$ ‐colourings of G $G$ by changing the colour of only one vertex at a time, while at each step maintaining a k $k$ ‐colouring? More generally, for a graph H $H$, the H $H$ ‐mixing problem asks: Can one obtain all homomorphisms G → H $G\to H$, starting from one homomorphism f $f$, by changing the image of only one vertex at a time, while at each step maintaining a homomorphism G → H $G\to H$ ? This paper focuses on a generalization of k $k$ ‐colourings, namely, ( p, q ) $(p, q)$ ‐circular colourings. We show that when 2 &lt; p q &lt; 4 $2\lt \frac{p}{q}\lt 4$, a graph G $G$ is ( p, q ) $(p, q)$ ‐mixing if and only if for any ( p, q ) $(p, q)$ ‐colouring f $f$ of G $G$, and any cycle C $C$ of G $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 ) $(p, q)$ ‐mixing is closed under a restricted homomorphism called a fold. Using this, we deduce that ( 2 k + 1, k ) $(2k+1, k)$ ‐mixing is co‐NP‐complete for all k ∈ N $k\in {\mathbb{N}}$, and by similar ideas we show that if the circular chromatic number of a connected graph G $G$ is 2 k + 1 k $\frac{2k+1}{k}$, then G $G$ folds to C 2 k + 1 ${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 ) $(p, q)$ ‐mixing in planar graphs when 3 ≤ p q &lt; 4 $3\le \frac{p}{q}\lt 4$ .