Dvořák–Feghali linear diameter conjecture for list recolouring of planar graphs
Dvořák–Feghali linear diameter conjecture for list recolouring of planar graphs
Let be a planar graph on vertices. A list assignment assigns a set of colours to each vertex , and let be the graph whose vertices are the proper -colourings of , with edges between colourings differing on exactly one vertex. Dvořák–Feghali's conjecture. If for every , then
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.