Dvořák–Feghali linear diameter conjecture for list recolouring of planar graphs

Let G=(V,E)G=(V,E) be a planar graph on nn vertices. A list assignment LL assigns a set L(v)L(v) of colours to each vertex vVv\in V, and let G(G,L)\mathcal{G}(G,L) be the graph whose vertices are the proper LL-colourings of GG, with edges between colourings differing on exactly one vertex. Dvořák–Feghali's conjecture. If L(v)10|L(v)|\geq 10 for every vVv\in V, then

G(G,L) has diameter O(n).\mathcal{G}(G,L)\text{ has diameter }O(n).

A linear bound is known for ordinary recolouring of planar graphs with ten colours, but the corresponding list-colouring statement remains the subject of the cited conjecture; the paper addresses it with further results.

Sources & referencesView supporting material

Primary source

Valentin Bartier, Nicolas Bousquet, Carl Feghali, Marc Heinrich, Benjamin Moore and Théo Pierron, “Recolouring planar graphs of girth at least five”, arXiv:2112.00631 (2021).

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.