Abstract
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.