The six-color conjecture for recoloring planar graphs of girth at least five
The six-color conjecture for recoloring planar graphs of girth at least five
Let be a planar graph of girth at least five on vertices. The graph is the reconfiguration graph whose vertices are proper -colorings of , with edges joining colorings that differ on one vertex.
Six-color conjecture. has diameter .
Planar graphs of girth at least five are colorable from lists of size three, and the paper explains that seven colors already suffice by a simpler argument. The conjectured bound improves this to six colors; no resolution is given in the supplied text.
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.