Publication at Faculty of Mathematics and Physics |
2020
Abstract
The reconfiguration graph Rk(G) of the k-colorings of a graph G has as vertex set the set of all possible k-colorings of G and two colorings are adjacent if they differ on the color of exactly one vertex. Cereceda conjectured 10 years ago that, for every k-degenerate graph G on n vertices, Rk+2(G) has diameter O(n^2).
The conjecture is wide open, with a best known bound of O(k^n), even for planar graphs. We improve this bound for planar graphs to 2^O(sqrt(n)).