Short and local transformations between (Δ+1)-colorings
Bousquet, Nicolas1; Feuilloley, Laurent1; Heinrich, Marc2; Rabie, Mikaël3
1 CNRS, INSA Lyon, UCBL, LIRIS, UMR5205, F-69621, Lyon, France
2 Leeds University, UK
3 Université Paris Cité, CNRS, IRIF, F-75013, Paris, France
Innovations in Graph Theory, Volume 2 (2025), pp. 119-156.

Recoloring a graph is about finding a sequence of proper colorings of this graph from an initial coloring σ to a target coloring η. Adding the constraint that each pair of consecutive colorings must differ on exactly one vertex, one asks: Is there a sequence of colorings from σ to η? If yes, how short can it be?

In this paper, we focus on (Δ+1)-colorings of graphs of maximum degree Δ. 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 Δ 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.

Received:
Accepted:
Published online:
DOI: 10.5802/igt.8
Keywords: Graph reconfiguration, recoloring, linear transformation, unfrozen colorings, distributed algorithms.

Bousquet, Nicolas 1; Feuilloley, Laurent 1; Heinrich, Marc 2; Rabie, Mikaël 3

1 CNRS, INSA Lyon, UCBL, LIRIS, UMR5205, F-69621, Lyon, France
2 Leeds University, UK
3 Université Paris Cité, CNRS, IRIF, F-75013, Paris, France
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@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},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {2},
     year = {2025},
     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. https://igt.centre-mersenne.org/articles/10.5802/igt.8/

[1] Barenboim, Leonid; Elkin, Michael Distributed Graph Coloring: Fundamentals and Recent Developments, Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers, 2013 | DOI | MR

[2] Barenboim, Leonid; Elkin, Michael; Kuhn, Fabian Distributed (Δ+1)-Coloring in Linear (in Δ) Time, SIAM J. Comput., Volume 43 (2014) no. 1, pp. 72-95 | DOI | MR | Zbl

[3] Bartier, Valentin; Bousquet, Nicolas; Feghali, Carl; Heinrich, Marc; Moore, Benjamin; Pierron, Théo Recoloring Planar Graphs of Girth at Least Five, SIAM J. Discret. Math., Volume 37 (2023) no. 1, pp. 332-350 | DOI | MR | Zbl

[4] Bonamy, Marthe; Bousquet, Nicolas Recoloring graphs via tree decompositions, Eur. J. Comb., Volume 69 (2018), pp. 200-213 | DOI | MR | Zbl

[5] Bonamy, Marthe; Bousquet, Nicolas; Perarnau, Guillem Frozen (Δ+ 1)-colourings of bounded degree graphs, Combinatorics, Probability and Computing, Volume 30 (2021) no. 3, pp. 330-343 | DOI | MR | Zbl

[6] Bonamy, Marthe; Johnson, Matthew; Lignos, Ioannis; Patel, Viresh; Paulusma, Daniël Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs, Journal of Combinatorial Optimization (2012), pp. 1-12 | DOI | MR | Zbl

[7] Bonamy, Marthe; Ouvrard, Paul; Rabie, Mikaël; Suomela, Jukka; Uitto, Jara 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 | DOI | MR | Zbl

[8] Bonsma, Paul S.; Cereceda, Luis 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] Bousquet, Nicolas; Bartier, Valentin Linear Transformations Between Colorings in Chordal Graphs, 27th Annual European Symposium on Algorithms, ESA 2019 (2019), Paper no. 24, 15 pages | DOI | MR

[10] Bousquet, Nicolas; Feuilloley, Laurent; Heinrich, Marc; Rabie, Mikaël 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] Bousquet, Nicolas; Heinrich, Marc A polynomial version of Cereceda’s conjecture, Journal of Combinatorial Theory, Series B, Volume 155 (2022), pp. 1-16 | DOI | MR

[12] Bousquet, Nicolas; Perarnau, Guillem Fast recoloring of sparse graphs, Eur. J. Comb., Volume 52 (2016), pp. 1-11 | DOI | MR | Zbl

[13] Cambie, Stijn; Batenburg, Wouter Cames van; Cranston, Daniel W. Optimally reconfiguring list and correspondence colourings, Eur. J. Comb., Volume 115 (2024), Paper no. 103798 | DOI | MR | Zbl

[14] Censor-Hillel, Keren; Maus, Yannic; Peled, Shahar Romem; Tonoyan, Tigran 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] Censor-Hillel, Keren; Rabie, Mikaël Distributed reconfiguration of maximal independent sets, J. Comput. Syst. Sci., Volume 112 (2020), pp. 85-96 | DOI | MR

[16] Cereceda, Luis Mixing Graph Colourings, Ph. D. Thesis, London School of Economics and Political Science (2007)

[17] Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew Mixing 3-colourings in bipartite graphs, Eur. J. Comb., Volume 30 (2009) no. 7, pp. 1593-1606 | DOI | MR | Zbl

[18] Chen, Sitan; Delcourt, Michelle; Moitra, Ankur; Perarnau, Guillem; Postle, Luke 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 | DOI | MR | Zbl

[19] Diestel, Reinhard Graph Theory, Graduate Texts in Mathematics, 173, Springer-Verlag, Heidelberg, 2005

[20] Dvorák, Zdenek; Feghali, Carl A Thomassen-type method for planar graph recoloring, Eur. J. Comb., Volume 95 (2021), Paper no. 103319 | DOI | MR | Zbl

[21] Dyer, Martin; Flaxman, Abraham D.; Frieze, Alan M; Vigoda, Eric 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] Feghali, Carl Paths between colourings of sparse graphs, Eur. J. Comb., Volume 75 (2019), pp. 169-171 | DOI | MR | Zbl

[23] Feghali, Carl; Johnson, Matthew; Paulusma, Daniël 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] Frieze, Alan; Vigoda, Eric 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] Ghaffari, Mohsen; Kuhn, Fabian 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] Gupta, Siddharth; Kumar, Manish; Pai, Shreyas 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 | DOI | MR | Zbl

[27] van den Heuvel, Jan The Complexity of change, Part of London Mathematical Society Lecture Note Series, Cambridge University Press (2013), p. 409

[28] Nishimura, Naomi Introduction to reconfiguration, Algorithms, Volume 11 (2018) no. 4, Paper no. 52, 25 pages | DOI | Zbl

[29] Panconesi, Alessandro; Srinivasan, Aravind The local nature of Δ-coloring and its algorithmic applications, Combinatorica, Volume 15 (1995) no. 2, pp. 255-280 | DOI | MR | Zbl

[30] Peleg, David Distributed computing: a locality-sensitive approach, SIAM, 2000 | MR

[31] Suomela, Jukka Survey of local algorithms, ACM Computing Surveys (CSUR), Volume 45 (2013) no. 2, pp. 1-40 | DOI | Zbl

[32] Vigoda, Eric 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: