Fast recoloring of sparse graphs

In this paper, we show that for every graph of maximum average degree bounded away from dd and any two (d+1)(d+1)-colorings of it, one can transform one coloring into the other one within a polynomial number of vertex recolorings so that, at each step, the current coloring is proper. In particular, it implies that we can transform any 88-coloring of a planar graph into any other 88-coloring with a polynomial number of recolorings. These results give some evidence on a conjecture of Cereceda et al. (2009) which asserts that any (d+2)(d+2) coloring of a dd-degenerate graph can be transformed into any other one using a polynomial number of recolorings.

We also show that any (2d+2)(2d+2)-coloring of a dd-degenerate graph can be transformed into any other one with a linear number of recolorings.