Recoloring a graph is about finding a sequence of proper colorings of this graph from an initial coloring $\sigma $ to a target coloring $\eta $. Adding the constraint that each pair of consecutive colorings must differ on exactly one vertex, one asks: Is there a sequence of colorings from $\sigma $ to $\eta $? If yes, how short can it be?
In this paper, we focus on $(\Delta +1)$-colorings of graphs of maximum degree $\Delta $. Feghali, Johnson and Paulusma proved that, if both colorings are unfrozen (i.e. if we can change the color of at least one vertex), then a recoloring sequence of length at most quadratic in the size of the graph always exists. We improve their result by proving that there actually exists a linear transformation (assuming that $\Delta $ is a constant).
In addition, we prove that the core of our algorithm can be performed locally. Informally, this means that after some preprocessing, the color changes that a given vertex has to perform only depend on the colors of the vertices in a constant size neighborhood. We make this precise by designing of an efficient recoloring algorithm in the LOCAL model of distributed computing.
Accepted:
Published online:
Bousquet, Nicolas 1; Feuilloley, Laurent 1; Heinrich, Marc 2; Rabie, Mikaël 3
CC-BY 4.0
@article{IGT_2025__2__119_0,
author = {Bousquet, Nicolas and Feuilloley, Laurent and Heinrich, Marc and Rabie, Mika\"el},
title = {Short and local transformations between ($\Delta +1$)-colorings},
journal = {Innovations in Graph Theory},
pages = {119--156},
year = {2025},
publisher = {Stichting Innovations in Graph Theory},
volume = {2},
doi = {10.5802/igt.8},
language = {en},
url = {https://igt.centre-mersenne.org/articles/10.5802/igt.8/}
}
TY - JOUR AU - Bousquet, Nicolas AU - Feuilloley, Laurent AU - Heinrich, Marc AU - Rabie, Mikaël TI - Short and local transformations between ($\Delta +1$)-colorings JO - Innovations in Graph Theory PY - 2025 SP - 119 EP - 156 VL - 2 PB - Stichting Innovations in Graph Theory UR - https://igt.centre-mersenne.org/articles/10.5802/igt.8/ DO - 10.5802/igt.8 LA - en ID - IGT_2025__2__119_0 ER -
%0 Journal Article %A Bousquet, Nicolas %A Feuilloley, Laurent %A Heinrich, Marc %A Rabie, Mikaël %T Short and local transformations between ($\Delta +1$)-colorings %J Innovations in Graph Theory %D 2025 %P 119-156 %V 2 %I Stichting Innovations in Graph Theory %U https://igt.centre-mersenne.org/articles/10.5802/igt.8/ %R 10.5802/igt.8 %G en %F IGT_2025__2__119_0
Bousquet, Nicolas; Feuilloley, Laurent; Heinrich, Marc; Rabie, Mikaël. Short and local transformations between ($\Delta +1$)-colorings. Innovations in Graph Theory, Volume 2 (2025), pp. 119-156. doi: 10.5802/igt.8
[1] Distributed Graph Coloring: Fundamentals and Recent Developments, Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers, 2013 | MR | DOI
[2] Distributed ()-Coloring in Linear (in ) Time, SIAM J. Comput., Volume 43 (2014) no. 1, pp. 72-95 | MR | Zbl | DOI
[3] Recoloring Planar Graphs of Girth at Least Five, SIAM J. Discret. Math., Volume 37 (2023) no. 1, pp. 332-350 | DOI | MR | Zbl
[4] Recoloring graphs via tree decompositions, Eur. J. Comb., Volume 69 (2018), pp. 200-213 | DOI | MR | Zbl
[5] Frozen (+ 1)-colourings of bounded degree graphs, Combinatorics, Probability and Computing, Volume 30 (2021) no. 3, pp. 330-343 | DOI | MR | Zbl
[6] Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs, Journal of Combinatorial Optimization (2012), pp. 1-12 | DOI | MR | Zbl
[7] Distributed Recoloring, 32nd International Symposium on Distributed Computing, DISC 2018 (LIPIcs), Volume 121, Schloss Dagstuhl - Leibniz-Zentrum für Informatk (2018), Paper no. 12, 17 pages | Zbl | DOI | MR
[8] Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances, Theor. Comput. Sci., Volume 410 (2009) no. 50, pp. 5215-5226 | DOI | MR | Zbl
[9] Linear Transformations Between Colorings in Chordal Graphs, 27th Annual European Symposium on Algorithms, ESA 2019 (2019), Paper no. 24, 15 pages | DOI | MR
[10] Distributed Recoloring of Interval and Chordal Graphs, 25th International Conference on Principles of Distributed Systems, OPODIS 2021 (Bramas, Quentin; Gramoli, Vincent; Milani, Alessia, eds.) (LIPIcs), Volume 217 (2021), Paper no. 19, 17 pages | DOI | MR
[11] A polynomial version of Cereceda’s conjecture, Journal of Combinatorial Theory, Series B, Volume 155 (2022), pp. 1-16 | DOI | MR
[12] Fast recoloring of sparse graphs, Eur. J. Comb., Volume 52 (2016), pp. 1-11 | DOI | MR | Zbl
[13] Optimally reconfiguring list and correspondence colourings, Eur. J. Comb., Volume 115 (2024), Paper no. 103798 | Zbl | DOI | MR
[14] Distributed Vertex Cover Reconfiguration, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022 (LIPIcs), Volume 215 (2022), Paper no. 36, 23 pages | DOI | MR | Zbl
[15] Distributed reconfiguration of maximal independent sets, J. Comput. Syst. Sci., Volume 112 (2020), pp. 85-96 | DOI | MR
[16] Mixing Graph Colourings, Ph. D. Thesis, London School of Economics and Political Science (2007)
[17] Mixing 3-colourings in bipartite graphs, Eur. J. Comb., Volume 30 (2009) no. 7, pp. 1593-1606 | MR | Zbl | DOI
[18] Improved Bounds for Randomly Sampling Colorings via Linear Programming, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 (2019), pp. 2216-2234 | MR | Zbl | DOI
[19] Graph Theory, Graduate Texts in Mathematics, 173, Springer-Verlag, Heidelberg, 2005
[20] A Thomassen-type method for planar graph recoloring, Eur. J. Comb., Volume 95 (2021), Paper no. 103319 | MR | Zbl | DOI
[21] Randomly coloring sparse random graphs with fewer colors than the maximum degree, Random Structures & Algorithms, Volume 29 (2006) no. 4, pp. 450-465 | DOI | MR | Zbl
[22] Paths between colourings of sparse graphs, Eur. J. Comb., Volume 75 (2019), pp. 169-171 | DOI | MR | Zbl
[23] A Reconfigurations Analogue of Brooks’ Theorem and Its Consequences, Journal of Graph Theory, Volume 83 (2016) no. 4, pp. 340-358 | DOI | MR | Zbl
[24] A survey on the use of Markov chains to randomly sample colourings, Oxford Lecture Series in Mathematics and its Applications, Volume 34 (2007), pp. 53-71 | Zbl
[25] Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition, 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, IEEE (2021), pp. 1009-1020 | DOI
[26] Brief Announcement: Distributed Reconfiguration of Spanning Trees, Stabilization, Safety, and Security of Distributed Systems - 24th International Symposium, SSS 2022, Volume 13751 (2022), pp. 346-351 | MR | Zbl | DOI
[27] The Complexity of change, Part of London Mathematical Society Lecture Note Series, Cambridge University Press (2013), p. 409
[28] Introduction to reconfiguration, Algorithms, Volume 11 (2018) no. 4, Paper no. 52, 25 pages | DOI | Zbl
[29] The local nature of -coloring and its algorithmic applications, Combinatorica, Volume 15 (1995) no. 2, pp. 255-280 | DOI | MR | Zbl
[30] Distributed computing: a locality-sensitive approach, SIAM, 2000 | MR
[31] Survey of local algorithms, ACM Computing Surveys (CSUR), Volume 45 (2013) no. 2, pp. 1-40 | DOI | Zbl
[32] Improved Bounds for Sampling Colorings, 40th Annual Symposium on Foundations of Computer Science, FOCS ’99, 17-18 October, 1999, New York, NY, USA (1999), pp. 51-59 | DOI | MR
Cited by Sources: