The list-recoloring conjecture for planar graphs
The list-recoloring conjecture for planar graphs
Let be a planar graph on vertices, let be a list assignment for , 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)$, thencan be transformed to by recolorings, with every intermediate coloring a proper -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
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.