Characterizing circular colouring mixing for pq<4 pq4. Issue 2 (5th August 2022) - Brewster, Richard C.; Moore, Benjamin
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→ 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→ H ? This paper focuses on a generalization of k k ‐colourings, namely, ( p, q ) (p, q) ‐circular colourings. We show that when 2 < p q < 4 2pq4, 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 kN, and by similar ideas we show that if the circular chromatic number of a connected graph G G is 2 k + 1 k 2k+1k, 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 < 4 3pq4 .