We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

A reconfigurations analogue of Brooks' Theorem and its consequences.

Feghali, Carl and Johnson, Matthew and Paulusma, Daniel (2016) 'A reconfigurations analogue of Brooks' Theorem and its consequences.', Journal of graph theory., 83 (4). pp. 340-358.


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.

Item Type:Article
Keywords:Graph coloring, Reconfigurations, Brooks’ Theorem.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher 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 This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.
Date accepted:24 September 2015
Date deposited:09 November 2015
Date of first online publication:27 October 2015
Date first made open access:27 October 2016

Save or Share this output

Look up in GoogleScholar