Cereceda's quadratic recoloring diameter conjecture for degenerate graphs

Let GG be a dd-degenerate graph, and let Rt(G)R_t(G) be the graph whose vertices are the proper tt-colorings of GG, with two colorings adjacent when they differ on one vertex. The tt-recoloring diameter is the maximum distance between two vertices of Rt(G)R_t(G), with disconnected Rt(G)R_t(G) having infinite diameter. Cereceda's conjecture. The tt-recoloring diameter of GG is at most quadratic when td+2t \ge d+2. This would improve the known connectivity result for dd-degenerate graphs to a quadratic bound on the number of single-vertex recolorings needed between any two proper colorings; the source does not state that the conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Yichen Wang and Mei Lu, “Linear recoloring diameter of degenerate chordal graphs and bounded treewidth graphs”, arXiv:2509.15456 (2025).

Additional references

7 papers in this index state this conjecture (2019–2025). The statement above is taken from the most recent of them; the others are arXiv:2509.03190, arXiv:2301.03417, arXiv:2209.05992, arXiv:2002.05383, arXiv:1907.01863, arXiv:1904.12698.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.