2022/03/16 by Bousquet, Nicolas, Feuilloley, Laurent, Heinrich, Marc +1
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2203.08885
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 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 Δ 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.