Flow reconfiguration with one modulus for all graphs, and Cereceda's conjecture for bipartite 2-degenerate graphs
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 . Parts I and II are about flows. For a finite multigraph and an integer , let be the graph on the nowhere-zero -flows of , and the graph on the integer flows of with on every edge; two flows are adjacent if the support of their difference is a cycle. We prove that and are connected for every finite bridgeless loopless multigraph if , if , or if is a multiple of with . This answers their Problem 1.2. The same holds for , for every prime power with , and for a set of moduli of natural density one; these results do not cover every . A master theorem for finite abelian groups gives the connectivity of the flow graph for every abelian group of order , and a binary form of it for every abelian group of exponent dividing and order at least , in particular (Esperet et al. proved ). Part III is about colourings: two proper -colourings of a graph are adjacent if they differ at exactly one vertex. Cereceda conjectured that this graph has diameter for every -degenerate graph on vertices and ; the case is open. For four colours we prove the diameter bound for every bipartite graph of degeneracy at most , with the order sharp in this class, also at girth ; the bound when an independent set of vertices of degree at most is added; and, with a computer-verified certificate, for every graph of cone width at most , a class that contains all graphs of treewidth at most and some graphs of treewidth with triangles.
Provenance statement
References
- 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
- V. Bartier, N. Bousquet, M. Heinrich, Recoloring graphs of treewidth 2, Discrete Math.\ 344 (2021) 112553; arXiv:2012.11459.arXiv
- H. L. Bodlaender, A partial -arboretum of graphs with bounded treewidth, Theoret.\ Comput.\ Sci.\ 209 (1998) 1--45.
- M. Bonamy, N. Bousquet, Recoloring graphs via tree decompositions, European J.\ Combin.\ 69 (2018) 200--213; arXiv:1403.6386.arXiv
- 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.
- 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.
- N. Bousquet, M. Heinrich, A polynomial version of Cereceda's conjecture, J.\ Combin.\ Theory Ser.\ B 155 (2022) 1--16; arXiv:1903.05619.arXiv
- N. Bousquet, G. Perarnau, Fast recoloring of sparse graphs, European J.\ Combin.\ 52 (2016) 1--11; arXiv:1411.6997.arXiv
- A. L. Cauchy, Recherches sur les nombres , J. École Polytech. 9 (1813), 99--116.
- L. Cereceda, Mixing graph colourings, PhD thesis, London School of Economics, 2007.
Show all 42 referencesShow fewer references
- L. Cereceda, J. van den Heuvel, M. Johnson, Finding paths between 3-colorings, J.\ Graph Theory 67 (2011) 69--82.
- D. W. Cranston, List-recoloring of sparse graphs, European J.\ Combin.\ 105 (2022) 103562; arXiv:2201.05133.arXiv
- D. W. Cranston, J. Li, B. Su, Z. Wang, and N. Xu, Reconfiguration of nowhere-zero flows , arXiv:2606.24685v1, 2026.arXiv
- D. W. Cranston, R. Mahmoud, -coloring reconfiguration of planar graphs with no short odd cycles, J.\ Graph Theory 105 (2024) 670--679; arXiv:2208.02228.arXiv
- H. Davenport, On the addition of residue classes , J. London Math. Soc. 10 (1935), 30--32.
- 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.
- 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
- 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
- C. Feghali, Reconfiguring colorings of graphs with bounded maximum average degree, J.\ Combin.\ Theory Ser.\ B 147 (2021) 133--138; arXiv:1904.12698.arXiv
- 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
- W. Feller, An Introduction to Probability Theory and Its Applications , Vol. I, 3rd ed., Wiley, New York, 1968.
- 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
- C. Godsil and G. Royle, Algebraic Graph Theory , Graduate Texts in Mathematics 207, Springer, New York, 2001.
- 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.
- L. A. Goldberg, R. Martin, M. Paterson, Random sampling of -colorings in , Random Structures Algorithms 24 (2004) 279--302.
- G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers , 6th ed., Oxford University Press, Oxford, 2008.
- A. J. Hoffman, Some recent applications of the theory of linear inequalities to extremal combinatorial analysis , Proc. Sympos. Appl. Math. 10 (1960), 113--127.
- 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
- 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.
- 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
- 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
- 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
- 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.
- C. Pan, W. Wang, R. Liu, List-recoloring of two classes of planar graphs, arXiv:2510.17628 (2025).arXiv
- D. J. Rose, R. E. Tarjan, G. S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM J.\ Comput.\ 5 (1976) 266--283.
- P. D. Seymour, Nowhere-zero -flows , J. Combin. Theory Ser. B 30 (1981), 130--135.
- W. T. Tutte, A contribution to the theory of chromatic polynomials , Canad. J. Math. 6 (1954), 80--91.
- W. T. Tutte, On the problem of decomposing a graph into 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
- A. G. Vosper, The critical pairs of subsets of a group of prime order , J. London Math. Soc. 31 (1956), 200--205.
- Y. Wang, M. Lu, Linear recoloring diameter of degenerate chordal graphs and bounded treewidth graphs, arXiv:2509.15456 (2025).arXiv
- M. E. Watkins, Connectivity of transitive graphs , J. Combin. Theory 8 (1970), 23--29.
- R. Zheng, J. Lu, The diameter of recoloring graphs under a maximum average degree bound, arXiv:2609.32688 (2026).arXiv
Version history
- 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