Toward Cereceda's conjecture for planar graphs
Eduard Eiben, Carl Feghali · Journal of Graph Theory · 2019
Abstract The reconfiguration graph of the ‐colorings of a graph has as vertex set the set of all possible ‐colorings of and two colorings are adjacent if they differ on the color of exactly one vertex. Cereceda conjectured 10 years ago that, for every ‐degenerate graph on vertices, has diameter . The conjecture is wide open, with a best known bound of , even for planar graphs. We improve this bound for planar graphs to . Our proof can be transformed into an algorithm that runs in time.