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.
References
Primary source
Nicolas Bousquet, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta and Amadeus Reinald, “Digraph redicolouring”, arXiv:2301.03417 (2023).
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.