Premium
Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings
Author(s) -
Brewster Richard C.,
Noel Jonathan A.
Publication year - 2015
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21846
Subject(s) - mathematics , homomorphism , combinatorics , corollary , mixing (physics) , homotopy , vertex (graph theory) , extension (predicate logic) , discrete mathematics , graph , pure mathematics , physics , quantum mechanics , computer science , programming language
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 ( k , q ) ‐colorings of a graph G can be obtained by successively recoloring a single vertex provided k / q ≥ 2 c o l ( G ) 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 ( k , q ) ‐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.