Research Library

Premium Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings
Author(s)
Brewster Richard C.,
Noel Jonathan A.
Publication year2015
Publication title
journal of graph theory
Resource typeJournals
PublisherWiley
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 ( 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.
Subject(s)combinatorics , corollary , discrete mathematics , graph , homomorphism , homotopy , mathematics , mixing (physics) , physics , pure mathematics , quantum mechanics , vertex (graph theory)
Language(s)English
SCImago Journal Rank1.164
H-Index54
eISSN1097-0118
pISSN0364-9024
DOI10.1002/jgt.21846

Seeing content that should not be on Zendy? Contact us.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here