The six-color conjecture for recoloring planar graphs of girth at least five

Let GG be a planar graph of girth at least five on nn vertices. The graph R6(G)R_6(G) is the reconfiguration graph whose vertices are proper 66-colorings of GG, with edges joining colorings that differ on one vertex.

Six-color conjecture. R6(G)R_6(G) has diameter O(n)O(n).

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

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.