{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T20:25:14Z","timestamp":1768335914293,"version":"3.49.0"},"reference-count":32,"publisher":"MathDoc\/Centre Mersenne","license":[{"start":{"date-parts":[[2025,3,7]],"date-time":"2025-03-07T00:00:00Z","timestamp":1741305600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>\n                    Recoloring a graph is about finding a sequence of proper colorings of this graph from an initial coloring\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>\u03c3<\/mml:mi>\n                    <\/mml:math>\n                    to a target coloring\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>\u03b7<\/mml:mi>\n                    <\/mml:math>\n                    . Adding the constraint that each pair of consecutive colorings must differ on exactly one vertex, one asks: Is there a sequence of colorings from\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>\u03c3<\/mml:mi>\n                    <\/mml:math>\n                    to\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>\u03b7<\/mml:mi>\n                    <\/mml:math>\n                    ? If yes, how short can it\u00a0be?\n                  <\/jats:p>\n                  <jats:p>\n                    In this paper, we focus on\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>\u0394<\/mml:mi>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    -colorings of graphs of maximum degree\u00a0\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>\u0394<\/mml:mi>\n                    <\/mml:math>\n                    . 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\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>\u0394<\/mml:mi>\n                    <\/mml:math>\n                    is a constant).\n                  <\/jats:p>\n                  <jats:p>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.<\/jats:p>","DOI":"10.5802\/igt.8","type":"journal-article","created":{"date-parts":[[2025,3,7]],"date-time":"2025-03-07T06:06:32Z","timestamp":1741327592000},"page":"119-156","source":"Crossref","is-referenced-by-count":0,"title":["Short and local transformations between (\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>\u0394<\/mml:mi>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    )-colorings"],"prefix":"10.5802","volume":"2","author":[{"given":"Nicolas","family":"Bousquet","sequence":"first","affiliation":[{"name":"CNRS, INSA Lyon, UCBL, LIRIS, UMR5205, F-69621, Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laurent","family":"Feuilloley","sequence":"additional","affiliation":[{"name":"CNRS, INSA Lyon, UCBL, LIRIS, UMR5205, F-69621, Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Heinrich","sequence":"additional","affiliation":[{"name":"Leeds University, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mika\u00ebl","family":"Rabie","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris Cit\u00e9, CNRS, IRIF, F-75013, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"3842","published-online":{"date-parts":[[2025,3,7]]},"reference":[{"key":"key2025121216553126745_1","doi-asserted-by":"publisher","DOI":"10.2200\/S00520ED1V01Y201307DCT011","author":"Barenboim, Leonid","year":"2013","unstructured":"[1] Barenboim, Leonid; Elkin, Michael Distributed Graph Coloring: Fundamentals and Recent Developments, Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers, 2013","journal-title":"Distributed Graph Coloring: Fundamentals and Recent Developments"},{"issue":"1","key":"key2025121216553126745_2","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1137\/12088848X","article-title":"Distributed (<span class=\"mathjax-formula\" data-tex=\"$\\Delta +1$\"><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mrow><mi>\u0394<\/mi><mo>+<\/mo><mn>1<\/mn><\/mrow><\/math><\/span>)-Coloring in Linear (in <span class=\"mathjax-formula\" data-tex=\"$\\Delta $\"><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mi>\u0394<\/mi><\/math><\/span>) Time","volume":"43","author":"Barenboim, Leonid","year":"2014","unstructured":"[2] Barenboim, Leonid; Elkin, Michael; Kuhn, Fabian Distributed (\u0394+1)-Coloring in Linear (in \u0394) Time, SIAM J. Comput., Volume 43 (2014) no. 1, pp. 72-95","journal-title":"SIAM J. Comput."},{"issue":"1","key":"key2025121216553126745_3","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1137\/21m1463598","article-title":"Recoloring Planar Graphs of Girth at Least Five","volume":"37","author":"Bartier, Valentin","year":"2023","unstructured":"[3] Bartier, Valentin; Bousquet, Nicolas; Feghali, Carl; Heinrich, Marc; Moore, Benjamin; Pierron, Th\u00e9o Recoloring Planar Graphs of Girth at Least Five, SIAM J. Discret. Math., Volume 37 (2023) no. 1, pp. 332-350","journal-title":"SIAM J. Discret. Math."},{"key":"key2025121216553126745_4","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/j.ejc.2017.10.010","article-title":"Recoloring graphs via tree decompositions","volume":"69","author":"Bonamy, Marthe","year":"2018","unstructured":"[4] Bonamy, Marthe; Bousquet, Nicolas Recoloring graphs via tree decompositions, Eur. J. Comb., Volume 69 (2018), pp. 200-213","journal-title":"Eur. J. Comb."},{"issue":"3","key":"key2025121216553126745_5","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1017\/S0963548320000139","article-title":"Frozen (<span class=\"mathjax-formula\" data-tex=\"$\\Delta $\"><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mi>\u0394<\/mi><\/math><\/span>+ 1)-colourings of bounded degree graphs","volume":"30","author":"Bonamy, Marthe","year":"2021","unstructured":"[5] Bonamy, Marthe; Bousquet, Nicolas; Perarnau, Guillem Frozen (\u0394+ 1)-colourings of bounded degree graphs, Combinatorics, Probability and Computing, Volume 30 (2021) no. 3, pp. 330-343","journal-title":"Combinatorics, Probability and Computing"},{"key":"key2025121216553126745_6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10878-012-9490-y","article-title":"Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs","author":"Bonamy, Marthe","year":"2012","unstructured":"[6] Bonamy, Marthe; Johnson, Matthew; Lignos, Ioannis; Patel, Viresh; Paulusma, Dani\u00ebl Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs, Journal of Combinatorial Optimization (2012), pp. 1-12","journal-title":"Journal of Combinatorial Optimization"},{"key":"key2025121216553126745_7","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2018.12","article-title":"Distributed Recoloring","volume":"121","author":"Bonamy, Marthe","year":"2018","unstructured":"[7] Bonamy, Marthe; Ouvrard, Paul; Rabie, Mika\u00ebl; Suomela, Jukka; Uitto, Jara Distributed Recoloring, 32nd International Symposium on Distributed Computing, DISC 2018 (LIPIcs), Volume 121, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatk (2018), 12, 17 pages","journal-title":"32nd International Symposium on Distributed Computing, DISC 2018"},{"issue":"50","key":"key2025121216553126745_8","doi-asserted-by":"publisher","first-page":"5215","DOI":"10.1016\/j.tcs.2009.08.023","article-title":"Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances","volume":"410","author":"Bonsma, Paul S.","year":"2009","unstructured":"[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","journal-title":"Theor. Comput. Sci."},{"key":"key2025121216553126745_9","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2019.24","article-title":"Linear Transformations Between Colorings in Chordal Graphs","author":"Bousquet, Nicolas","year":"2019","unstructured":"[9] Bousquet, Nicolas; Bartier, Valentin Linear Transformations Between Colorings in Chordal Graphs, 27th Annual European Symposium on Algorithms, ESA 2019 (2019), 24, 15 pages","journal-title":"27th Annual European Symposium on Algorithms, ESA 2019"},{"key":"key2025121216553126745_10","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.OPODIS.2021.19","article-title":"Distributed Recoloring of Interval and Chordal Graphs","volume":"217","author":"Bousquet, Nicolas","year":"2021","unstructured":"[10] Bousquet, Nicolas; Feuilloley, Laurent; Heinrich, Marc; Rabie, Mika\u00ebl 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), 19, 17 pages","journal-title":"25th International Conference on Principles of Distributed Systems, OPODIS 2021"},{"key":"key2025121216553126745_11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jctb.2022.01.006","article-title":"A polynomial version of Cereceda\u2019s conjecture","volume":"155","author":"Bousquet, Nicolas","year":"2022","unstructured":"[11] Bousquet, Nicolas; Heinrich, Marc A polynomial version of Cereceda\u2019s conjecture, Journal of Combinatorial Theory, Series B, Volume 155 (2022), pp. 1-16","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"key2025121216553126745_12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejc.2015.08.001","article-title":"Fast recoloring of sparse graphs","volume":"52","author":"Bousquet, Nicolas","year":"2016","unstructured":"[12] Bousquet, Nicolas; Perarnau, Guillem Fast recoloring of sparse graphs, Eur. J. Comb., Volume 52 (2016), pp. 1-11","journal-title":"Eur. J. Comb."},{"key":"key2025121216553126745_13","doi-asserted-by":"publisher","DOI":"10.1016\/J.EJC.2023.103798","article-title":"Optimally reconfiguring list and correspondence colourings","volume":"115","author":"Cambie, Stijn","year":"2024","unstructured":"[13] Cambie, Stijn; Batenburg, Wouter Cames van; Cranston, Daniel W. Optimally reconfiguring list and correspondence colourings, Eur. J. Comb., Volume 115 (2024), 103798","journal-title":"Eur. J. Comb."},{"key":"key2025121216553126745_14","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2022.36","article-title":"Distributed Vertex Cover Reconfiguration","volume":"215","author":"Censor-Hillel, Keren","year":"2022","unstructured":"[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), 36, 23 pages","journal-title":"13th Innovations in Theoretical Computer Science Conference, ITCS 2022"},{"key":"key2025121216553126745_15","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jcss.2020.03.003","article-title":"Distributed reconfiguration of maximal independent sets","volume":"112","author":"Censor-Hillel, Keren","year":"2020","unstructured":"[15] Censor-Hillel, Keren; Rabie, Mika\u00ebl Distributed reconfiguration of maximal independent sets, J. Comput. Syst. Sci., Volume 112 (2020), pp. 85-96","journal-title":"J. Comput. Syst. Sci."},{"key":"key2025121216553126745_16","author":"Cereceda, Luis","year":"2007","unstructured":"[16] Cereceda, Luis Mixing Graph Colourings, Ph. D. Thesis, London School of Economics and Political Science (2007)","journal-title":"Mixing Graph Colourings"},{"issue":"7","key":"key2025121216553126745_17","doi-asserted-by":"publisher","first-page":"1593","DOI":"10.1016\/j.ejc.2009.03.011","article-title":"Mixing 3-colourings in bipartite graphs","volume":"30","author":"Cereceda, Luis","year":"2009","unstructured":"[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","journal-title":"Eur. J. Comb."},{"key":"key2025121216553126745_18","doi-asserted-by":"publisher","first-page":"2216","DOI":"10.1137\/1.9781611975482.134","article-title":"Improved Bounds for Randomly Sampling Colorings via Linear Programming","author":"Chen, Sitan","year":"2019","unstructured":"[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","journal-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019"},{"key":"key2025121216553126745_19","volume":"173","author":"Diestel, Reinhard","year":"2005","unstructured":"[19] Diestel, Reinhard Graph Theory, Graduate Texts in Mathematics, 173, Springer-Verlag, Heidelberg, 2005","journal-title":"Graph Theory"},{"key":"key2025121216553126745_20","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2021.103319","article-title":"A Thomassen-type method for planar graph recoloring","volume":"95","author":"Dvor\u00e1k, Zdenek","year":"2021","unstructured":"[20] Dvor\u00e1k, Zdenek; Feghali, Carl A Thomassen-type method for planar graph recoloring, Eur. J. Comb., Volume 95 (2021), 103319","journal-title":"Eur. J. Comb."},{"issue":"4","key":"key2025121216553126745_21","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1002\/rsa.20129","article-title":"Randomly coloring sparse random graphs with fewer colors than the maximum degree","volume":"29","author":"Dyer, Martin","year":"2006","unstructured":"[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 &amp; Algorithms, Volume 29 (2006) no. 4, pp. 450-465","journal-title":"Random Structures & Algorithms"},{"key":"key2025121216553126745_22","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.ejc.2018.09.001","article-title":"Paths between colourings of sparse graphs","volume":"75","author":"Feghali, Carl","year":"2019","unstructured":"[22] Feghali, Carl Paths between colourings of sparse graphs, Eur. J. Comb., Volume 75 (2019), pp. 169-171","journal-title":"Eur. J. Comb."},{"issue":"4","key":"key2025121216553126745_23","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1002\/jgt.22000","article-title":"A Reconfigurations Analogue of Brooks\u2019 Theorem and Its Consequences","volume":"83","author":"Feghali, Carl","year":"2016","unstructured":"[23] Feghali, Carl; Johnson, Matthew; Paulusma, Dani\u00ebl A Reconfigurations Analogue of Brooks\u2019 Theorem and Its Consequences, Journal of Graph Theory, Volume 83 (2016) no. 4, pp. 340-358","journal-title":"Journal of Graph Theory"},{"key":"key2025121216553126745_24","first-page":"53","article-title":"A survey on the use of Markov chains to randomly sample colourings","volume":"34","author":"Frieze, Alan","year":"2007","unstructured":"[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","journal-title":"Oxford Lecture Series in Mathematics and its Applications"},{"key":"key2025121216553126745_25","doi-asserted-by":"publisher","first-page":"1009","DOI":"10.1109\/FOCS52979.2021.00101","article-title":"Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition","author":"Ghaffari, Mohsen","year":"2021","unstructured":"[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","journal-title":"62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021"},{"key":"key2025121216553126745_26","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/978-3-031-21017-4_25","article-title":"Brief Announcement: Distributed Reconfiguration of Spanning Trees","volume":"13751","author":"Gupta, Siddharth","year":"2022","unstructured":"[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","journal-title":"Stabilization, Safety, and Security of Distributed Systems - 24th International Symposium, SSS 2022"},{"key":"key2025121216553126745_27","first-page":"409","author":"van den Heuvel, Jan","year":"2013","unstructured":"[27] van den Heuvel, Jan The Complexity of change, Part of London Mathematical Society Lecture Note Series, Cambridge University Press (2013), p. 409","journal-title":"The Complexity of change"},{"issue":"4","key":"key2025121216553126745_28","doi-asserted-by":"publisher","DOI":"10.3390\/a11040052","article-title":"Introduction to reconfiguration","volume":"11","author":"Nishimura, Naomi","year":"2018","unstructured":"[28] Nishimura, Naomi Introduction to reconfiguration, Algorithms, Volume 11 (2018) no. 4, 52, 25 pages","journal-title":"Algorithms"},{"issue":"2","key":"key2025121216553126745_29","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF01200759","article-title":"The local nature of <span class=\"mathjax-formula\" data-tex=\"$\\Delta $\"><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mi>\u0394<\/mi><\/math><\/span>-coloring and its algorithmic applications","volume":"15","author":"Panconesi, Alessandro","year":"1995","unstructured":"[29] Panconesi, Alessandro; Srinivasan, Aravind The local nature of \u0394-coloring and its algorithmic applications, Combinatorica, Volume 15 (1995) no. 2, pp. 255-280","journal-title":"Combinatorica"},{"key":"key2025121216553126745_30","author":"Peleg, David","year":"2000","unstructured":"[30] Peleg, David Distributed computing: a locality-sensitive approach, SIAM, 2000","journal-title":"Distributed computing: a locality-sensitive approach"},{"issue":"2","key":"key2025121216553126745_31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2431211.2431223","article-title":"Survey of local algorithms","volume":"45","author":"Suomela, Jukka","year":"2013","unstructured":"[31] Suomela, Jukka Survey of local algorithms, ACM Computing Surveys (CSUR), Volume 45 (2013) no. 2, pp. 1-40","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"key2025121216553126745_32","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1109\/SFFCS.1999.814577","article-title":"Improved Bounds for Sampling Colorings","author":"Vigoda, Eric","year":"1999","unstructured":"[32] Vigoda, Eric Improved Bounds for Sampling Colorings, 40th Annual Symposium on Foundations of Computer Science, FOCS \u201999, 17-18 October, 1999, New York, NY, USA (1999), pp. 51-59","journal-title":"40th Annual Symposium on Foundations of Computer Science, FOCS \u201999, 17-18 October, 1999, New York, NY, USA"}],"container-title":["Innovations in Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/igt.centre-mersenne.org\/item\/10.5802\/igt.8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T15:55:41Z","timestamp":1765554941000},"score":1,"resource":{"primary":{"URL":"https:\/\/igt.centre-mersenne.org\/articles\/10.5802\/igt.8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,7]]},"references-count":32,"alternative-id":["10.5802\/igt.8"],"URL":"https:\/\/doi.org\/10.5802\/igt.8","relation":{},"ISSN":["3050-743X"],"issn-type":[{"value":"3050-743X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,7]]}}}