Digraph analogue of Cereceda's diameter conjecture

About 3 years old · traced to

Let DD be a digraph on nn vertices, and let δmin⁡∗(D)\delta^*_{\min}(D) denote its min-degeneracy. Let Dk(D){\cal D}_k(D) be the graph whose vertices are the kk-dicolourings of DD, with adjacency given by recolouring one vertex. Digraph Cereceda conjecture. If k≥δmin⁡∗(D)+2k\geq \delta^*_{\min}(D)+2, then the diameter of Dk(D){\cal D}_k(D) is at most O(n2)O(n^2). 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

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.