HEXAGONbeta

The Cereceda (2007) conjecture holds for bipartite 2-degenerate graphs

A mix of human-written and AI-generated textHuman understanding: some partsmath.CO — Combinatoricscs.DM — Discrete Mathematics

Contributed by Dave Goel ↗

Version 1 / Nov 10, 2026 / CC BY-SA 4.0

Abstract

For a graph GG and a positive integer kk, the kk-recolouring graph Rk(G)\mathcal{R}_{k}(G) has the proper kk-colourings of GG as vertices, two of them adjacent when they differ at exactly one vertex. A graph is dd-degenerate if each of its non-empty subgraphs has a vertex of degree at most dd. The Cereceda (2007) conjecture states that, for fixed dd and k≥d+2k \ge d+2, the diameter of Rk(G)\mathcal{R}_{k}(G) is O(n2)O(n^2) for every dd-degenerate graph GG on nn vertices. For d=2d = 2, the conjecture was known to hold for k≥5k \ge 5 by a result of Cereceda; for k=4k = 4, the best bound known for all 22-degenerate graphs is O(n3)O(n^3), due to Bousquet and Heinrich. We prove that the diameter of R4(G)\mathcal{R}_{4}(G) is at most 2n(n+1)2n(n+1) for every bipartite 22-degenerate graph GG on nn vertices; hence the conjecture holds for these graphs. We also show that the order n2n^2 cannot be improved for this class, even for graphs of girth 66. For the upper bound, we fix an ordering of the vertices in which each vertex has at most two later neighbours. In nn stages, we transform any proper 44-colouring into the colouring in which every vertex has the least colour not used by its later neighbours, recolouring each vertex at most twice per stage. Both of our bounds have also been proved in the Lean proof assistant.

Author comments: An expanded version of this paper, with many other results, is posted on Zenodo: https://doi.org/10.5281/zenodo.23603237

Provenance statement

This work was done overwhelmingly by AI models and supervised by the author. The models were Anthropic's Claude and OpenAI's ChatGPT. The author takes full responsibility for the paper.

References

  1. V. Bartier, N. Bousquet, C. Feghali, M. Heinrich, B. Moore, T. Pierron, Recoloring planar graphs of girth at least five, SIAM J.\ Discrete Math.\ 37 (2023) 332--350; arXiv:2112.00631.arXiv
  2. T. Biedl, A. Lubiw, O. Merkel, Building a larger class of graphs for efficient reconfiguration of vertex colouring, in: Extended Abstracts EuroComb 2021, Trends Math.\ 14, Birkhäuser, 2021, 286--292; full version: arXiv:2003.01818.arXiv
  3. M. Bonamy, N. Bousquet, Recoloring graphs via tree decompositions, European J.\ Combin.\ 69 (2018) 200--213; arXiv:1403.6386.arXiv
  4. M. Bonamy, M. Johnson, I. Lignos, V. Patel, D. Paulusma, Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs, J.\ Comb.\ Optim.\ 27 (2014) 132--143; open version: HAL lirmm-00782882.
  5. P. Bonsma, L. Cereceda, Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances, Theoret.\ Comput.\ Sci.\ 410 (2009) 5215--5226; open version: TU Berlin DepositOnce (preprint of 18 May 2007), doi:10.14279/depositonce-14393.DOI
  6. N. Bousquet, L. Feuilloley, M. Heinrich, M. Rabie, Short and local transformations between (Δ+1)(\Delta+1)-colorings, Innov.\ Graph Theory 2 (2025) 119--156; arXiv:2203.08885.arXiv
  7. N. Bousquet, M. Heinrich, A polynomial version of Cereceda's conjecture, J.\ Combin.\ Theory Ser.\ B 155 (2022) 1--16; arXiv:1903.05619.arXiv
  8. N. Bousquet, G. Perarnau, Fast recoloring of sparse graphs, European J.\ Combin.\ 52 (2016) 1--11; arXiv:1411.6997.arXiv
  9. L. Cereceda, Mixing graph colourings, PhD thesis, London School of Economics, 2007; https://researchonline.lse.ac.uk/id/eprint/131216.link
  10. L. Cereceda, J. van den Heuvel, M. Johnson, Connectedness of the graph of vertex-colourings, Discrete Math.\ 308 (2008) 913--919.
Show all 17 referencesShow fewer references
  1. L. Cereceda, J. van den Heuvel, M. Johnson, Finding paths between 3-colorings, J.\ Graph Theory 67 (2011) 69--82.
  2. D. W. Cranston, R. Mahmoud, 5-Coloring reconfiguration of planar graphs with no short odd cycles, J.\ Graph Theory 105 (2024) 670--679; arXiv:2208.02228.arXiv
  3. M. Dyer, A. D. Flaxman, A. M. Frieze, E. Vigoda, Randomly coloring sparse random graphs with fewer colors than the maximum degree, Random Structures Algorithms 29 (2006) 450--465.
  4. C. Feghali, Reconfiguring colorings of graphs with bounded maximum average degree, J.\ Combin.\ Theory Ser.\ B 147 (2021) 133--138; arXiv:1904.12698.arXiv
  5. C. Feghali, M. Johnson, D. Paulusma, A reconfigurations analogue of Brooks' theorem and its consequences, J.\ Graph Theory 83 (2016) 340--358; arXiv:1501.05800.arXiv
  6. D. Goel, Flow reconfiguration with one modulus for all graphs, and Cereceda's conjecture for bipartite 2-degenerate graphs, Zenodo (2026), version 2.30, doi:10.5281/zenodo.23603237 (https://doi.org/10.5281/zenodo.23603237).DOI
  7. L. A. Goldberg, R. Martin, M. Paterson, Random sampling of 33-colorings in Z2\mathbb{Z}^2, Random Structures Algorithms 24 (2004) 279--302.

Version history

  1. v1 · 17 pagesSubmitted by Dave GoelAn expanded version of this paper, with many other results, is posted on Zenodo: https://doi.org/10.5281/zenodo.23603237CurrentNov 10, 2026