Short and local transformations between (Δ+1)-colorings

• DOI: 10.5802/igt.8
• Publication Date: 2025-03-07T11:06:32Z
• Authors: Nicolas Bousquet; Laurent Feuilloley; Marc Heinrich; Mikaël Rabie

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.