Polynomial recoloring diameter conjecture for planar graphs
Let be a planar graph and let be an integer. The -recoloring graph has vertices corresponding to proper -colorings of , with edges joining colorings that differ on one vertex by one color. Polynomial recoloring diameter conjecture. For every planar graph and every integer , the graph 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
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.