Polynomial recoloring diameter conjecture for planar graphs

From papers

Let GG be a planar graph and let kk be an integer. The kk-recoloring graph Rk(G)R_k(G) has vertices corresponding to proper kk-colorings of GG, with edges joining colorings that differ on one vertex by one color. Polynomial recoloring diameter conjecture. For every planar graph GG and every integer k7k\geq 7, the graph Rk(G)R_k(G) has polynomial diameter. This would establish a polynomial recoloring bound for planar graphs with at least seven colors; the statement is presented as a question for further work, and no resolution is given here.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Marthe Bonamy and Nicolas Bousquet, “Recoloring graphs via tree decompositions”, arXiv:1403.6386 (2014).

Additional references

2 papers in this index state this conjecture (2013–2014). The statement above is taken from the most recent of them; the others are arXiv:1302.3486.

Solutions 0

No solutions have been posted yet.