Mixing Homomorphisms,Recolorings, and Extending Circular Precolorings |
| |
| Authors: | Richard C Brewster Jonathan A Noel |
| |
| Affiliation: | 1. DEPARTMENT OF MATHEMATICS AND STATISTICS, THOMPSON RIVERS UNIVERSITY, BRITISH COLUMBIA, CANADAContract grant sponsor: Natural Science and Engineering Research Council of Canada (NSERC).;2. MATHEMATICAL INSTITUTE, UNIVERSITY OF OXFORD, UNITED KINGDOMContract grant sponsor: Thompson Rivers University;3. contract grant sponsor: NSERC Undergraduate Student Research Awards program. |
| |
| Abstract: | 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. |
| |
| Keywords: | coloring homomorphism mixing coloring extension discrete homotopy dismantlablility |
|
|
