Digraph analogue of Cereceda's diameter conjecture
Digraph analogue of Cereceda's diameter conjecture
Let be a digraph on vertices, and let denote its min-degeneracy. Let be the graph whose vertices are the -dicolourings of , with adjacency given by recolouring one vertex. Digraph Cereceda conjecture. If , then the diameter of is at most . This conjecture extends Cereceda's quadratic-diameter conjecture from graphs to digraphs; the paper proves linear-diameter results for larger colour ranges, but the stated quadratic bound remains open.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Nicolas Bousquet, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta and Amadeus Reinald, “Digraph redicolouring”, arXiv:2301.03417 (2023).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.