Polynomial recoloring diameter conjecture for planar graphs

About 13 years old · traced to

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 k≥7k\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.

References

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.

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.