论文标题
$（δ+ 1）$ - 边缘色的快速分布式算法
A Fast Distributed Algorithm for $(Δ+ 1)$-Edge-Coloring
论文作者
论文摘要
我们在本地模型中提出了确定性分布式算法，该算法找到了适当的$（δ+ 1）$ - $ n $ vertex的最大度$δ$ in $ \ mathrm {poly}（δ，\ log n）$ n）的$ n $ vertex图。这是第一个仅使用$δ+1 $颜色（与Viping的定理给出的限制）的第一个非平凡分布式边缘色算法。我们的方法灵感来自于Grebík和Pikhurko引起的Viping定理的最新证明。
We present a deterministic distributed algorithm in the LOCAL model that finds a proper $(Δ+ 1)$-edge-coloring of an $n$-vertex graph of maximum degree $Δ$ in $\mathrm{poly}(Δ, \log n)$ rounds. This is the first nontrivial distributed edge-coloring algorithm that uses only $Δ+1$ colors (matching the bound given by Vizing's theorem). Our approach is inspired by the recent proof of the measurable version of Vizing's theorem due to Grebík and Pikhurko.
