Towards the locality of Vizing’s theorem
Hsin-Hao Su, Hoa T. Vu · 2019
Vizing showed that it suffices to color the edges of a simple graph using Δ + 1 colors, where Δ is the maximum degree of the graph. However, up to this date, no efficient distributed edge-coloring algorithm is known for obtaining such coloring, even for constant degree graphs. The current algorithms that get closest to this number of colors are the randomized (Δ + Θ(√Δ))-edge-coloring algorithm that runs in (n) rounds by Chang et al. [SODA 2018] and the deterministic (Δ + (n))-edge-coloring algorithm that runs in (Δ, logn) rounds by Ghaffari et al. [STOC 2018].