math.CO — Combinatorics
Flow reconfiguration with one modulus for all graphs, and Cereceda's conjecture for bipartite 2-degenerate graphs
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.