  One of the fundamental and most-studied algorithmic problems in distributed
computing on networks is graph coloring, both in bounded-degree and in general
graphs. Recently, the study of this problem has been extended in two
directions. First, the problem of recoloring, that is computing an efficient
transformation between two given colorings (instead of computing a new
coloring), has been considered, both to model radio network updates, and as a
useful subroutine for coloring. Second, as it appears that general graphs and
bounded-degree graphs do not model real networks very well (with, respectively,
pathological worst-case topologies and too strong assumptions), coloring has
been studied in more specific graph classes. In this paper, we study the
intersection of these two directions: distributed recoloring in two relevant
graph classes, interval and chordal graphs.
