论文标题
（$δ+1 $）之间的短暂和本地转换 - 着色
Short and local transformations between ($Δ+1$)-colorings
论文作者
论文摘要
重新上色图是关于从初始着色$σ$到目标着色$η$的一系列适当着色的序列。加上一个约束，即每对连续的着色必须在一个顶点上完全不同，一个人问：是否有一系列着色序列从$σ$到$η$？如果是，它有多短？ 在本文中，我们专注于$（δ+1）$ - 最高度$δ$的图形颜色。 Feghali，Johnson和Paulusma证明，如果两种颜色都不冷（即我们可以更改一个至少一个顶点的颜色），则始终存在二次重新上色序列。我们通过证明实际上存在线性转换来改善他们的结果（假设$δ$是常数）。 此外，我们证明可以在本地执行算法的核心。非正式地，这意味着经过一些预处理后，给定节点必须执行的颜色更改仅取决于恒定尺寸邻域中顶点的颜色。我们通过在分布式计算的局部模型中设计有效的重新下色算法来确切地做到这一点。
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.
