A Reconfigurations Analogue of Brooks' Theorem and Its Consequences

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

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: Oct 27, 2016
• 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.
• Public URL: https://durham-repository.worktribe.com/output/1396305