Flow reconfiguration with one modulus for all graphs, and Cereceda's conjecture for bipartite 2-degenerate graphs

A mix of human-written and AI-generated textHuman understanding: some partsmath.CO — Combinatorics

Contributed by Dave Goel ↗

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

Abstract

This paper answers a question of Esperet, Hendrey, Lagoutte, Marseloo, Norin and Steiner on flow reconfiguration and makes inroads into Cereceda's recolouring conjecture for d=2d=2. Parts I and II are about flows. For a finite multigraph GG and an integer k≥2k\ge 2, let Mk(G)M_k(G) be the graph on the nowhere-zero Zk\mathbb{Z}_k-flows of GG, and Ik(G)I_k(G) the graph on the integer flows FF of GG with 1≤∣F(e)∣≤k−11\le|F(e)|\le k-1 on every edge; two flows are adjacent if the support of their difference is a cycle. We prove that Mk(G)M_k(G) and Ik(G)I_k(G) are connected for every finite bridgeless loopless multigraph GG if k=40k=40, if k=48k=48, or if kk is a multiple of 44 with k≥52k\ge 52. This answers their Problem 1.2. The same holds for k=66k=66, for every prime power pNp^N with N≥6N\ge 6, and for a set of moduli of natural density one; these results do not cover every k≥40k\ge 40. A master theorem for finite abelian groups gives the connectivity of the flow graph F(G,Γ)F(G,\Gamma) for every abelian group Γ\Gamma of order 4040, and a binary form of it for every abelian group of exponent dividing 44 and order at least 3232, in particular F25\mathbb{F}_2^5 (Esperet et al. proved F28\mathbb{F}_2^8). Part III is about colourings: two proper kk-colourings of a graph GG are adjacent if they differ at exactly one vertex. Cereceda conjectured that this graph has diameter O(n2)O(n^2) for every dd-degenerate graph on nn vertices and k=d+2k=d+2; the case d=2d=2 is open. For four colours we prove the diameter bound 2n(n+1)2n(n+1) for every bipartite graph of degeneracy at most 22, with the order n2n^2 sharp in this class, also at girth 66; the bound 5n(n+1)5n(n+1) when an independent set of vertices of degree at most 22 is added; and, with a computer-verified certificate, 4n(n+1)4n(n+1) for every graph of cone width at most 22, a class that contains all graphs of treewidth at most 22 and some graphs of treewidth 33 with triangles.

Author comments: First version: October 23, 2026. This is the expanded version, with many other results, of the paper "The Cereceda (2007) conjecture holds for bipartite 2-degenerate graphs", which is at https://hexagonmath.org/2611.00260 on Hexagon. The ancillary files of this paper (programs and data) are at https://doi.org/10.5281/zenodo.23603238 on Zenodo.

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. V. Bartier, N. Bousquet, M. Heinrich, Recoloring graphs of treewidth 2, Discrete Math.\ 344 (2021) 112553; arXiv:2012.11459.arXiv
  3. H. L. Bodlaender, A partial kk-arboretum of graphs with bounded treewidth, Theoret.\ Comput.\ Sci.\ 209 (1998) 1--45.
  4. M. Bonamy, N. Bousquet, Recoloring graphs via tree decompositions, European J.\ Combin.\ 69 (2018) 200--213; arXiv:1403.6386.arXiv
  5. 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; author version HAL lirmm-00782882.
  6. P. Bonsma, L. Cereceda, Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances, Theoret.\ Comput.\ Sci.\ 410 (2009) 5215--5226; preprint of 18 May 2007, TU Berlin DepositOnce.
  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. A. L. Cauchy, Recherches sur les nombres , J. École Polytech. 9 (1813), 99--116.
  10. L. Cereceda, Mixing graph colourings, PhD thesis, London School of Economics, 2007.
Show all 42 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, List-recoloring of sparse graphs, European J.\ Combin.\ 105 (2022) 103562; arXiv:2201.05133.arXiv
  3. D. W. Cranston, J. Li, B. Su, Z. Wang, and N. Xu, Reconfiguration of nowhere-zero flows , arXiv:2606.24685v1, 2026.arXiv
  4. D. W. Cranston, R. Mahmoud, 55-coloring reconfiguration of planar graphs with no short odd cycles, J.\ Graph Theory 105 (2024) 670--679; arXiv:2208.02228.arXiv
  5. H. Davenport, On the addition of residue classes , J. London Math. Soc. 10 (1935), 30--32.
  6. 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.
  7. J. Edmonds, Submodular functions, matroids, and certain polyhedra , in: Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, 1969), Gordon and Breach, New York, 1970, pp. 69--87; reprinted in: Combinatorial Optimization -- Eureka, You Shrink! , Lecture Notes in Comput. Sci. 2570, Springer, Berlin, 2003, pp. 11--26, doi:10.1007/3-540-36478-1_2 (https://doi.org/10.1007/3-540-36478-1_2).DOI
  8. L. Esperet, K. Hendrey, A. Lagoutte, M. Marseloo, S. Norin, and R. Steiner, Nowhere-zero flow reconfiguration , arXiv:2512.17342v4 (https://arxiv.org/abs/2512.17342v4), July 3, 2026.arXiv
  9. C. Feghali, Reconfiguring colorings of graphs with bounded maximum average degree, J.\ Combin.\ Theory Ser.\ B 147 (2021) 133--138; arXiv:1904.12698.arXiv
  10. 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
  11. W. Feller, An Introduction to Probability Theory and Its Applications , Vol. I, 3rd ed., Wiley, New York, 1968.
  12. H. Fleischner, B. Bagheri Gh. and B. Klocker, Perfect pseudo-matchings in cubic graphs , Graphs Combin. 40 (2024), Article 118, doi:10.1007/s00373-024-02844-y (https://doi.org/10.1007/s00373-024-02844-y).DOI
  13. C. Godsil and G. Royle, Algebraic Graph Theory , Graduate Texts in Mathematics 207, Springer, New York, 2001.
  14. D. Goel, Eulerian graphs are flow-connected: a proof of a conjecture of Cranston, Li, Su, Wang and Xu , unpublished manuscript, version 2.00, October 8, 2026.
  15. L. A. Goldberg, R. Martin, M. Paterson, Random sampling of 33-colorings in Z2\mathbb{Z}^2, Random Structures Algorithms 24 (2004) 279--302.
  16. G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers , 6th ed., Oxford University Press, Oxford, 2008.
  17. A. J. Hoffman, Some recent applications of the theory of linear inequalities to extremal combinatorial analysis , Proc. Sympos. Appl. Math. 10 (1960), 113--127.
  18. F. Jaeger, Flows and generalized coloring theorems in graphs , J. Combin. Theory Ser. B 26 (1979), 205--216, doi:10.1016/0095-8956(79)90057-1 (https://doi.org/10.1016/0095-8956(79)90057-1).DOI
  19. F. Jaeger, Nowhere-zero flow problems , in: L. W. Beineke and R. J. Wilson (eds.), Selected Topics in Graph Theory 3 , Academic Press, London, 1988, pp. 71--95.
  20. F. Jaeger, N. Linial, C. Payan and M. Tarsi, Group connectivity of graphs---a nonhomogeneous analogue of nowhere-zero flow properties , J. Combin. Theory Ser. B 56 (1992), 165--182, doi:10.1016/0095-8956(92)90016-Q (https://doi.org/10.1016/0095-8956(92)90016-Q).DOI
  21. W. Mader, Über den Zusammenhang symmetrischer Graphen , Arch. Math. (Basel) 21 (1970), 331--336, doi:10.1007/BF01220924 (https://doi.org/10.1007/BF01220924).DOI
  22. C. St.\ J. A. Nash-Williams, Edge-disjoint spanning trees of finite graphs , J. London Math. Soc. 36 (1961), 445--450, doi:10.1112/jlms/s1-36.1.445 (https://doi.org/10.1112/jlms/s1-36.1.445).DOI
  23. C. St.\ J. A. Nash-Williams, An application of matroids to graph theory , in: P. Rosenstiehl (ed.), Theory of Graphs (International Symposium, Rome, 1966), Gordon and Breach, New York, 1967, pp. 263--265; J. Edmonds, Matroid partition , in: G. B. Dantzig and A. F. Veinott, Jr. (eds.), Mathematics of the Decision Sciences, Part 1 , Lectures in Applied Mathematics 11, Amer. Math. Soc., Providence, RI, 1968, pp. 335--345.
  24. C. Pan, W. Wang, R. Liu, List-recoloring of two classes of planar graphs, arXiv:2510.17628 (2025).arXiv
  25. D. J. Rose, R. E. Tarjan, G. S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM J.\ Comput.\ 5 (1976) 266--283.
  26. P. D. Seymour, Nowhere-zero 66-flows , J. Combin. Theory Ser. B 30 (1981), 130--135.
  27. W. T. Tutte, A contribution to the theory of chromatic polynomials , Canad. J. Math. 6 (1954), 80--91.
  28. W. T. Tutte, On the problem of decomposing a graph into nn connected factors , J. London Math. Soc. 36 (1961), 221--230, doi:10.1112/jlms/s1-36.1.221 (https://doi.org/10.1112/jlms/s1-36.1.221).DOI
  29. A. G. Vosper, The critical pairs of subsets of a group of prime order , J. London Math. Soc. 31 (1956), 200--205.
  30. Y. Wang, M. Lu, Linear recoloring diameter of degenerate chordal graphs and bounded treewidth graphs, arXiv:2509.15456 (2025).arXiv
  31. M. E. Watkins, Connectivity of transitive graphs , J. Combin. Theory 8 (1970), 23--29.
  32. R. Zheng, J. Lu, The diameter of recoloring graphs under a maximum average degree bound, arXiv:2609.32688 (2026).arXiv

Version history

  1. v1 · 181 pagesSubmitted by Dave GoelFirst version: October 23, 2026. This is the expanded version, with many other results, of the paper "The Cereceda (2007) conjecture holds for bipartite 2-degenerate graphs", which is at https://hexagonmath.org/2611.00260 on Hexagon. The ancillary files of this paper (programs and data) are at https://doi.org/10.5281/zenodo.23603238 on Zenodo.CurrentNov 16, 2026