Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings
This work brings together ideas of mixing graph colorings, discrete homotopy, and precoloring extension. A particular focus is circular colorings. We prove that all the -colorings of a graph G can be obtained by successively recoloring a single vertex provided along the lines of Cereceda, van den Heuvel, and Johnson's result for k-colorings. We give various bounds for such mixing results and discuss their sharpness, including cases where the bounds for circular and classical colorings coincide. As a corollary, we obtain an Albertson-type extension theorem for -precolorings 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.
mixing homomorphism coloring discrete homotopy coloring extension dismantlablility