The list-recoloring conjecture for planar graphs

Let GG be a planar graph on nn vertices, let LL be a list assignment for GG, and let

and $'$ be $L$-colorings of $G$. A proper $L$-coloring assigns to each vertex a color from its list, with adjacent vertices receiving different colors. **List-recoloring conjecture.** If either - $|L(v)|\ge 10$ for every $v\in V(G)$, or - $G$ is triangle-free and $|L(v)|\ge 7$ for every $v\in V(G)$, then

can be transformed to ' by O(n)O(n) recolorings, with every intermediate coloring a proper LL-coloring.

The paper notes that its ordinary-coloring theorems likely generalize to list coloring, but does not establish this statement. The claim would extend the linear-diameter recoloring results from fixed color sets to vertex-specific lists.

Sources & referencesView supporting material

Primary source

Zdeněk Dvořák and Carl Feghali, “A Thomassen-type method for planar graph recoloring”, arXiv:2006.09269 (2020).

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.