Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich, and Mikael Rabie.
Innovations in Graph Theory 2025 doi: 10.5802/igt.8Abstract
Recoloring a graph is about finding a sequence of proper colorings of this graph from an initial coloring σ to a target coloring η. Adding the constraint that each pair of consecutive colorings must differ on exactly one vertex, one asks: Is there a sequence of colorings from σ to η? If yes, how short can it be?
In this paper, we focus on (∆ + 1)-colorings of graphs of maximum degree ∆. Feghali, Johnson and Paulusma proved that, if both colorings are unfrozen (i.e. if we can change the color of at least one vertex), then a recoloring sequence of length at most quadratic in the size of the graph always exists. We improve their result by proving that there actually exists a linear transformation (assuming that ∆ 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 vertex 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.