Regular Cereceda's Conjecture

About 4 years old · traced to

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

diam⁡Ck(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.

References

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.