A Reconfigurations Analogue of Brooks' Theorem and Its Consequences

作者：Feghali Carl^*; Johnson Matthew; Paulusma Daniel

来源：Journal of Graph Theory, 2016, 83(4): 340-358.

DOI：10.1002/jgt.22000

• graph coloring
• reconfigurations
• Brooks' Theorem

Let G be a simple undirected connected graph on n vertices with maximum degree Delta. Brooks' Theorem states that G has a proper Delta-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, k > Delta, a Delta-coloring of G can be obtained by a sequence of O(n(2)) recolorings using only the original k colors unless
- G is a complete graph or a cycle with an odd number of vertices, or
- k = Delta + 1, G is Delta-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 R-k(G) of the k-colorings of G. The vertex set of R-k(G) 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 Delta >= 3, R Lambda+1(G) consists of isolated vertices and at most one further component that has diameter O(n(2)). This result enables us to complete both a structural and an algorithmic characterization for reconfigurations of colorings of graphs of bounded maximum degree.

• 出版日期2016-12