Skip to main content

Research Repository

Advanced Search

A Reconfigurations Analogue of Brooks' Theorem and Its Consequences

Feghali, C.; Johnson, M.; Paulusma, D.

A Reconfigurations Analogue of Brooks' Theorem and Its Consequences Thumbnail


Authors

C. Feghali



Abstract

Let G be a simple undirected connected graph on n vertices with maximum degree Δ. Brooks' Theorem states that G has a proper Δ-coloring unless G is a complete graph, or a cycle with an odd number of vertices. To recolor G is to obtain a new proper coloring by changing the color of one vertex. We show an analogue of Brooks' Theorem by proving that from any k-coloring, inline image, a Δ-coloring of G can be obtained by a sequence of inline image recolorings using only the original k colors unless – G is a complete graph or a cycle with an odd number of vertices, or – inline image, G is Δ-regular and, for each vertex v in G, no two neighbors of v are colored alike. We use this result to study the reconfiguration graph inline image of the k-colorings of G. The vertex set of inline image is the set of all possible k-colorings of G and two colorings are adjacent if they differ on exactly one vertex. We prove that for inline image, inline image consists of isolated vertices and at most one further component that has diameter inline image. This result enables us to complete both a structural and an algorithmic characterization for reconfigurations of colorings of graphs of bounded maximum degree.

Citation

Feghali, C., Johnson, M., & Paulusma, D. (2016). A Reconfigurations Analogue of Brooks' Theorem and Its Consequences. Journal of Graph Theory, 83(4), 340-358. https://doi.org/10.1002/jgt.22000

Journal Article Type Article
Acceptance Date Sep 24, 2015
Online Publication Date Oct 27, 2015
Publication Date Dec 1, 2016
Deposit Date Oct 31, 2015
Publicly Available Date Mar 28, 2024
Journal Journal of Graph Theory
Print ISSN 0364-9024
Electronic ISSN 1097-0118
Publisher Wiley
Peer Reviewed Peer Reviewed
Volume 83
Issue 4
Pages 340-358
DOI https://doi.org/10.1002/jgt.22000
Keywords Graph coloring, Reconfigurations, Brooks’ Theorem.

Files

Accepted Journal Article (261 Kb)
PDF

Copyright Statement
This is the accepted version of the following article: Feghali, C., Johnson, M. and Paulusma, D. (2016), A Reconfigurations Analogue of Brooks' Theorem and Its Consequences. Journal of Graph Theory, 83(4): 340-358, which has been published in final form at http://dx.doi.org/10.1002/jgt.22000. This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.





You might also like



Downloadable Citations