{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T06:24:51Z","timestamp":1790749491963,"version":"4.1.0"},"reference-count":19,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-19-CE48-0013-01"],"award-info":[{"award-number":["ANR-19-CE48-0013-01"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-18-CE40-0032"],"award-info":[{"award-number":["ANR-18-CE40-0032"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["19-21082S"],"award-info":[{"award-number":["19-21082S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2023,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>For a positive integer [Formula: see text], the [Formula: see text]-recoloring graph of a graph [Formula: see text] has as vertex set all proper [Formula: see text]-colorings of [Formula: see text] with two [Formula: see text]-colorings being adjacent if they differ by the color of exactly one vertex. A result of Dyer et al. regarding graphs of bounded degeneracy implies that the 7-recoloring graphs of planar graphs, the 5-recoloring graphs of triangle-free planar graphs and the 4-recoloring graphs planar graphs of girth at least six are connected. On the other hand, there are planar graphs whose 6-recoloring graph is disconnected, triangle-free planar graphs whose 4-recoloring graph is disconnected, and planar graphs of any given girth whose 3-recoloring graph is disconnected. The main result of this paper consists in showing, via a novel application of the discharging method, that the 4-recoloring graph of every planar graph of girth five is connected. This completes the classification of the connectedness of the recoloring graph for planar graphs of given girth. We also prove some theorems regarding the diameter of the recoloring graph of planar graphs.<\/jats:p>","DOI":"10.1137\/21m1463598","type":"journal-article","created":{"date-parts":[[2023,2,22]],"date-time":"2023-02-22T10:30:35Z","timestamp":1677061835000},"page":"332-350","source":"Crossref","is-referenced-by-count":10,"title":["Recoloring Planar Graphs of Girth at Least Five"],"prefix":"10.1137","volume":"37","author":[{"given":"Valentin","family":"Bartier","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Lyon, EnsL, LIP, Lyon, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicolas","family":"Bousquet","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lyon, Universit\u00e9 Lyon 1, LIRIS, CNRS, Lyon, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carl","family":"Feghali","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lyon, CNRS, EnsL, LIP, Lyon, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4546-2359","authenticated-orcid":true,"given":"Marc","family":"Heinrich","sequence":"additional","affiliation":[{"name":"School of Computing, University of Leeds, Leeds LS2 9JT, United Kingdom."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benjamin","family":"Moore","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, Charles university, Prague, Czech Republic."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Th\u00e9o","family":"Pierron","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lyon, Universit\u00e9 Lyon 1, LIRIS, CNRS, Lyon, France."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,2,21]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2021.112553"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2017.10.010"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-012-9490-y"},{"key":"ref4","first-page":"9","volume":"46","author":"Borodin O.","year":"1989","journal-title":"Mat. Zametki"},{"key":"ref5","unstructured":"N. Bousquet  and \nV. Bartier , Linear transformations between colorings in chordal graphs, in Proceedings of the 27th Annual European Symposium on Algorithms, ESA 2019, 2019, 24."},{"key":"ref6","unstructured":"N. Bousquet  and \nM. Heinrich , A Polynomial Version of Cereceda\u2019s Conjecture, preprint, https:\/\/arxiv.org\/abs\/1903.05619, 2019."},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2015.08.001"},{"key":"ref8","unstructured":"L. Cereceda , Mixing Graph Colorings, Ph.D. thesis, London School of Economics and Political Science, 2007."},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2009.03.011"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"S. Chen , \nM. Delcourt , \nA. Moitra , \nG. Perarnau , and \nL. Postle , Improved bounds for randomly sampling colorings via linear programming, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, 2019, pp. 2216\u20132234.","DOI":"10.1137\/1.9781611975482.134"},{"key":"ref11","doi-asserted-by":"crossref","first-page":"P4.51","DOI":"10.37236\/9391","volume":"4","author":"Dvo\u0159\u00e1k Z.","year":"2020","journal-title":"Electron. J. Combin."},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2021.103319"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20129"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/140957883"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2020.11.001"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"A. Frieze  and \nE. Vigoda , A survey on the use of Markov chains to randomly sample colorings, in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh, \nG. Grimmett , and \nC. McDiarmid , eds. Oxford Lecture Ser. Math. Appl. 34, Oxford University Press, Oxford, UK, 2007, pp. 53\u201371.","DOI":"10.1093\/acprof:oso\/9780198571278.003.0004"},{"key":"ref17","first-page":"109","volume":"8","author":"Gr\u00f6tzsch H.","year":"1959","journal-title":"science Z. Martin Luther Univ. Halle-Wittenberg, Math. Nat. Line"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.3390\/a11040052"},{"key":"ref19","unstructured":"J. van den Heuvel , The Complexity of change, in Surveys of Combinatorics 2013, \nS. R. Blackburn , \nS. Gerke , and \nM. Wildon , eds. London Math. Soc. Lect. Note Ser. 409, Cambridge University Press, Cambridge, UK, 2013, pp. 127\u2013160."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1463598","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:39:28Z","timestamp":1787319568000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1463598"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,21]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3,31]]}},"alternative-id":["10.1137\/21M1463598"],"URL":"https:\/\/doi.org\/10.1137\/21m1463598","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,21]]}}}