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

About 5 years old · traced to

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 v∈Vv\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 v∈Vv\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.

References

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.