Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$
Richard C. Brewster, Benjamin R. Moore · Journal of Graph Theory · 2022
Abstract Given a graph , the ‐mixing problem asks: Starting with a ‐colouring of , can one obtain all ‐colourings of by changing the colour of only one vertex at a time, while at each step maintaining a ‐colouring? More generally, for a graph , the ‐mixing problem asks: Can one obtain all homomorphisms , starting from one homomorphism , by changing the image of only one vertex at a time, while at each step maintaining a homomorphism ? This paper focuses on a generalization of ‐colourings, namely, ‐circular colourings. We show that when , a graph is ‐mixing if and only if for any ‐colouring of , and any cycle of , 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 ‐mixing is closed under a restricted homomorphism called a fold. Using this, we deduce that ‐mixing is co‐NP‐complete for all , and by similar ideas we show that if the circular chromatic number of a connected graph is , then folds to . 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 ‐mixing in planar graphs when .