Linear-diameter conjectures for list-recolouring graphs

About 5 years old · traced to

Let GG be a connected graph with nn vertices, and let LL be a list-assignment of GG. Write C(G,L)\mathcal{C}(G,L) for the LL-recolouring graph and C^(G,L)\widehat{\mathcal{C}}(G,L) for the corresponding relaxed recolouring graph. Linear-diameter conjectures. (a) If, in addition to the conditions in the Key Lemma, GG has minimum degree at least 33, then C(G,L)\mathcal{C}(G,L) is connected and has diameter O(n)O(n). (b) If, in addition to the conditions in the Main Theorem, GG has minimum degree at least 33, then C^(G,L)\widehat{\mathcal{C}}(G,L) is connected and has diameter O(n)O(n). (c) If, in addition to the conditions in the Main Theorem, GG has no path of degree-22 vertices of length more than tt for some t≥0t\geq0, then C^(G,L)\widehat{\mathcal{C}}(G,L) is connected and has diameter O((t+1)n)O((t+1)n). These conjectures seek linear, or controlled near-linear, diameter bounds beyond the quadratic diameter forced by long induced paths of degree-22 vertices. The supplied passage does not provide evidence that any of the three claims has been resolved.

References

Primary source

Stijn Cambie, Wouter Cames van Batenburg, Daniel W. Cranston, Jan van den Heuvel and Ross J. Kang, “Reconfiguration of List Colourings”, arXiv:2505.08020 (2025).

Additional references

3 papers in this index state this conjecture (2021–2025). The statement above is taken from the most recent of them; the others are arXiv:2301.04881, arXiv:2112.00631.

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.