The Library
Mixing homomorphisms, recolorings, and extending circular precolorings
Tools
Brewster, Richard C. and Noel, Jonathan A. (2015) Mixing homomorphisms, recolorings, and extending circular precolorings. Journal of Graph Theory, 80 (3). pp. 173-198. doi:10.1002/jgt.21846 ISSN 0364-9024.
|
PDF
WRAP-mixing-homomorphisms-circular-precolorings-Noel-2015.pdf - Accepted Version - Requires a PDF viewer. Download (849Kb) | Preview |
Official URL: http://dx.doi.org/10.1002/jgt.21846
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 ≥ 2 col (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
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Graph coloring, Homotopy theory | ||||||
Journal or Publication Title: | Journal of Graph Theory | ||||||
Publisher: | John Wiley & Sons Ltd. | ||||||
ISSN: | 0364-9024 | ||||||
Official Date: | November 2015 | ||||||
Dates: |
|
||||||
Volume: | 80 | ||||||
Number: | 3 | ||||||
Page Range: | pp. 173-198 | ||||||
DOI: | 10.1002/jgt.21846 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 10 July 2018 | ||||||
Date of first compliant Open Access: | 10 July 2018 | ||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year