Research Repository

# A Reconfigurations Analogue of Brooks' Theorem and Its Consequences

## 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 Sep 24, 2015 Oct 27, 2015 Dec 1, 2016 Oct 31, 2015 Oct 27, 2016 Journal of Graph Theory 0364-9024 1097-0118 Wiley Peer Reviewed 83 4 340-358 https://doi.org/10.1002/jgt.22000 Graph coloring, Reconfigurations, Brooks’ Theorem. https://durham-repository.worktribe.com/output/1396305

#### Files

Accepted Journal Article (261 Kb)
PDF