Abstract
Let G be a simple undirected graph on n vertices with maximum degree Δ. Brooks’ Theorem states that G has a Δ-colouring unless G is a complete graph, or a cycle with an odd number of vertices. To recolour G is to obtain a new proper colouring by changing the colour of one vertex. We show that from a k-colouring, k > Δ, a Δ-colouring of G can be obtained by a sequence of O(n 2) recolourings using only the original k colours unless
-
G is a complete graph or a cycle with an odd number of vertices, or
-
k = Δ + 1, G is Δ-regular and, for each vertex v in G, no two neighbours of v are coloured alike.
We use this result to study the reconfiguration graph R k (G) of the k-colourings of G. The vertex set of R k (G) is the set of all possible k-colourings of G and two colourings are adjacent if they differ on exactly one vertex. It is known that
-
if k ≤ Δ(G), then R k (G) might not be connected and it is possible that its connected components have superpolynomial diameter,
-
if k ≥ Δ(G) + 2, then R k (G) is connected and has diameter O(n 2).
We complete this structural classification by settling the missing case:
-
if k = Δ(G) + 1, then R k (G) consists of isolated vertices and at most one further component which has diameter O(n 2).
We also describe completely the computational complexity classification of the problem of deciding whether two k-colourings of a graph G of maximum degree Δ belong to the same component of R k (G) by settling the case k = Δ(G) + 1. The problem is
-
O(n 2) time solvable for k = 3,
-
PSPACE-complete for 4 ≤ k ≤ Δ(G),
-
O(n) time solvable for k = Δ(G) + 1,
-
O(1) time solvable for k ≥ Δ(G) + 2 (the answer is always yes).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bonamy, M., Bousquet, N.: Recoloring bounded treewidth graphs. In: Proc. LAGOS 2013. Electronic Notes in Discrete Mathematics, vol. 44, pp. 257–262 (2013)
Bonamy, M., Johnson, M., Lignos, I.M., Patel, V., Paulusma, D.: Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Journal of Combinatorial Optimization 27, 132–143 (2014)
Bonsma, P.: The complexity of rerouting shortest paths. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 222–233. Springer, Heidelberg (2012)
Bonsma, P.: Rerouting shortest paths in planar graphs. In: Proc. FSTTCS 2012. LIPIcs, vol. 18, pp. 337–349 (2012)
Bonsma, P., Cereceda, L.: Finding paths between graph colourings: Pspace-completeness and superpolynomial distances. Theoretical Computer Science 410, 5215–5226 (2009)
Bonsma, P., Kamiński, M., Wrochna, M.: Reconfiguring independent sets in claw-free graphs. arXiv, 1403.0359 (2014)
Bonsma, P., Mouawad, A.: The complexity of bounded length graph recoloring. arXiv, 1404.0337 (2014)
Brooks, R.L.: On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society 37, 194–197 (1941)
Cereceda, L.: Mixing graph colourings. PhD thesis, London School of Economics (2007)
Cereceda, L., van den Heuvel, J., Johnson, M.: Connectedness of the graph of vertex-colourings. Discrete Mathematics 308, 913–919 (2008)
Cereceda, L., van den Heuvel, J., Johnson, M.: Mixing 3-colourings in bipartite graphs. European Journal of Combinatorics 30(7), 1593–1606 (2009)
Cereceda, L., van den Heuvel, J., Johnson, M.: Finding paths between 3-colorings. Journal of Graph Theory 67(1), 69–82 (2011)
Gopalan, P., Kolaitis, P.G., Maneva, E.N., Papadimitriou, C.H.: The connectivity of boolean satisfiability: Computational and structural dichotomies. SIAM Journal on Computing 38(6), 2330–2355 (2009)
van den Heuvel, J.: The complexity of change. In: Blackburn, S.R., Gerke, S., Wildon, M. (eds.) Surveys in Combinatorics 2013, London. Mathematical Society Lecture Notes Series, vol. 409 (2013)
Ito, T., Demaine, E.D.: Approximability of the subset sum reconfiguration problem. In: Ogihara, M., Tarui, J. (eds.) TAMC 2011. LNCS, vol. 6648, pp. 58–69. Springer, Heidelberg (2011)
Ito, T., Demaine, E.D., Harvey, N.J.A., Papadimitriou, C.H., Sideri, M., Uehara, R., Uno, Y.: On the complexity of reconfiguration problems. Theoretical Computer Science 412(12-14), 1054–1065 (2011)
Ito, T., Kaminski, M., Demaine, E.D.: Reconfiguration of list edge-colorings in a graph. Discrete Applied Mathematics 160(15), 2199–2207 (2012)
Johnson, M., Kratsch, D., Kratsch, S., Patel, V., Paulusma, D.: Colouring reconfiguration is fixed-parameter tractable. arXiv, 1403.6347 (2014)
Kaminski, M., Medvedev, P., Milanic, M.: Shortest paths between shortest paths. Theoretical Computer Science 412(39), 5205–5210 (2011)
Kaminski, M., Medvedev, P., Milanic, M.: Complexity of independent set reconfigurability problems. Theoretical Computer Science 439, 9–15 (2012)
Makino, K., Tamaki, S., Yamamoto, M.: On the boolean connectivity problem for horn relations. Discrete Applied Mathematics 158(18), 2024–2030 (2010)
Melnikov, L.S., Vizing, V.G.: New proof of brooks’ theorem. Journal of Combinatorial Theory 7(4), 289–290 (1969)
Mouawad, A.E., Nishimura, N., Raman, V.: Vertex cover reconfiguration and beyond. arXiv, 1402.4926 (2014)
Mouawad, A.E., Nishimura, N., Raman, V., Simjour, N., Suzuki, A.: On the parameterized complexity of reconfiguration problems. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 281–294. Springer, Heidelberg (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Feghali, C., Johnson, M., Paulusma, D. (2014). A Reconfigurations Analogue of Brooks’ Theorem. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds) Mathematical Foundations of Computer Science 2014. MFCS 2014. Lecture Notes in Computer Science, vol 8635. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44465-8_25
Download citation
DOI: https://doi.org/10.1007/978-3-662-44465-8_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44464-1
Online ISBN: 978-3-662-44465-8
eBook Packages: Computer ScienceComputer Science (R0)