Id: hexagon/2611.00260 Pdf: https://hexagonmath.org/pdf/2611.00260v1 Url: https://hexagonmath.org/abs/2611.00260v1 Tags: cs.DM, msc:05C15, msc:05C85, Cereceda conjecture, bipartite graphs, degenerate graphs, graph recolouring, reconfiguration Score: 0 Title: The Cereceda (2007) conjecture holds for bipartite 2-degenerate graphs Domain: math.CO Origin: ai-generated Source: hexagon Authors: Dave Goel Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-11-10 Withdrawn: false Authorship: mixed Formalized: false Human-understanding: some Page: https://delphi.science/r/hexagon/2611.00260 For a graph $G$ and a positive integer $k$, the $k$-recolouring graph $\mathcal{R}_{k}(G)$ has the proper $k$-colourings of $G$ as vertices, two of them adjacent when they differ at exactly one vertex. A graph is $d$-degenerate if each of its non-empty subgraphs has a vertex of degree at most $d$. The Cereceda (2007) conjecture states that, for fixed $d$ and $k \ge d+2$, the diameter of $\mathcal{R}_{k}(G)$ is $O(n^2)$ for every $d$-degenerate graph $G$ on $n$ vertices. For $d = 2$, the conjecture was known to hold for $k \ge 5$ by a result of Cereceda; for $k = 4$, the best bound known for…