Digraph analogue of Cereceda's diameter conjecture

From papers

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.

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

No solutions have been posted yet.