A Fast Distributed Algorithm for $(\Delta +1)$-Edge-Coloring

Abstract

We present a deterministic distributed algorithm in the LOCAL model that finds a proper $(\Delta +1)$-edge-coloring of an $n$-vertex graph of maximum degree $\Delta$ in $\mathrm{poly}(\Delta ,\log n)$ rounds. This is the first nontrivial distributed edge-coloring algorithm that uses only $\Delta +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.

24 pages, 9 figures