Linear-diameter conjectures for list-recolouring graphs

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 t0t\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.

Sources & referencesView supporting material

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.