Regular Cereceda's Conjecture

Let GG be a dd-regular graph, let μ(G)\mu(G) denote its matching number, let n(G)n(G) denote its number of vertices, and let Ck(G)\mathcal{C}_k(G) be the reconfiguration graph of proper kk-colourings of GG.

Regular Cereceda's Conjecture. If k=d+2k=d+2, then

diamCk(G)=n(G)+μ(G).\operatorname{diam} \mathcal{C}_k(G)=n(G)+\mu(G).

This would combine the conjectured upper bound for list-colouring reconfiguration with the corresponding lower-bound question to determine the precise diameter at the threshold for regular graphs. It remains open.

Sources & referencesView supporting material

Primary source

Stijn Cambie, Wouter Cames van Batenburg and Daniel W. Cranston, “Optimally Reconfiguring List and Correspondence Colourings”, arXiv:2204.07928 (2023).

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.