Recoloring graphs via tree decompositions∗

Let k be an integer. Two vertex k-colorings of a graph are adjacent if they differ on exactly one vertex. A graph is k-mixing if any proper k-coloring can be transformed into any other through a sequence of adjacent proper k-colorings. Jerrum proved that any graph is k-mixing if k is at least the maximum degree plus two. We first improve Jerrum’s bound using the grundy number, which is the worst number of colors in a greedy coloring. Any graph is (tw + 2)-mixing, where tw is the treewidth of the graph (Cereceda 2006). We prove that the shortest sequence between any two (tw+2)-colorings is at most quadratic (which is optimal up to a constant factor), a problem left open in Bonamy et al. (2012). We also prove that given any two (χ(G)+1)-colorings of a cograph (resp. distance-hereditary graph) G, we can find a linear (resp. quadratic) sequence between them. In both cases, the bounds cannot be improved by more than a constant factor for a fixed χ(G). The graph classes are also optimal in some sense: one of the smallest interesting superclass of distance-hereditary graphs corresponds to comparability graphs, for which no such property holds (even when relaxing the constraint on the length of the sequence). As for cographs, they are equivalently the graphs with no induced P4, and there exist P5-free graphs that admit no sequence between two of their (χ(G) + 1)-colorings. All the proofs are constructivist and lead to polynomial-time recoloring algorithms