{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-10","reactions":{},"withdrawn":false,"authorship":"mixed","formalized":false,"human_understanding":"some"}