Mixing Homomorphisms, Recolourings, and Extending Circular Precolourings

Abstract

This work brings together ideas of mixing graph colourings, discrete homotopy, and precolouring extension. A particular focus is circular colourings. We prove that all the $(k,q)$-colourings of a graph $G$ can be obtained by successively recolouring a single vertex provided $k/q\ge 2col(G)$ along the lines of Cereceda, van den Heuvel and Johnson's result for $k$-colourings. We give various bounds for such mixing results and discuss their sharpness, including cases where the bounds for circular and classical colourings coincide. As a corollary, we obtain an Albertson-type extension theorem for $(k,q)$-precolourings of circular cliques. Such a result was first conjectured by Albertson and West. General results on homomorphism mixing are presented, including a characterization of graphs $G$ for which the endomorphism monoid can be generated through the mixing process. As in similar work of Brightwell and Winkler, the concept of dismantlability plays a key role.

29 pages, 2 figures