  Recoloring a graph is about finding a sequence of proper colorings of this
graph from an initial coloring $\sigma$ to a target coloring $\eta$. Adding the
constraint that each pair of consecutive colorings must differ on exactly one
vertex, one asks: Is there a sequence of colorings from $\sigma$ to $\eta$? If
yes, how short can it be?
  In this paper, we focus on $(\Delta+1)$-colorings of graphs of maximum degree
$\Delta$. Feghali, Johnson and Paulusma proved that, if both colorings are
non-frozen (i.e. we can change the color of a least one vertex), then a
quadratic recoloring sequence always exists. We improve their result by proving
that there actually exists a linear transformation (assuming that $\Delta$ is a
constant).
  In addition, we prove that the core of our algorithm can be performed
locally. Informally, this means that after some preprocessing, the color
changes that a given node has to perform only depend on the colors of the
vertices in a constant size neighborhood. We make this precise by designing of
an efficient recoloring algorithm in the LOCAL model of distributed computing.
