Linear-diameter conjectures for list-recolouring graphs
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.