Linear-diameter conjectures for list-recolouring graphs
Let be a connected graph with vertices, and let be a list-assignment of . Write for the -recolouring graph and for the corresponding relaxed recolouring graph. Linear-diameter conjectures. (a) If, in addition to the conditions in the Key Lemma, has minimum degree at least , then is connected and has diameter . (b) If, in addition to the conditions in the Main Theorem, has minimum degree at least , then is connected and has diameter . (c) If, in addition to the conditions in the Main Theorem, has no path of degree- vertices of length more than for some , then is connected and has diameter . These conjectures seek linear, or controlled near-linear, diameter bounds beyond the quadratic diameter forced by long induced paths of degree- 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
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.