Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence

We study the edge-coloring problem in the message-passing model of distributed computing. This is one of the most fun-damental problems in this area. Currently, the best-known deterministic algorithms for (2∆ − 1)-edge-coloring requires O(∆)+ log ∗ n time [23], where ∆ is the maximum degree of the input graph. Also, recent results of [5] for vertex-coloring imply that one can get anO(∆)-edge-coloring inO(∆ϵ·logn) time, and an O(∆1+ϵ)-edge-coloring in O(log ∆ log n) time, for an arbitrarily small constant ϵ> 0. In this paper we devise a significantly faster deterministic edge-coloring algorithm. Specifically, our algorithm com-putes an O(∆)-edge-coloring in O(∆ϵ) + log ∗ n time, and an O(∆1+ϵ)-edge-coloring in O(log∆) + log ∗ n time. This result improves the state-of-the-art running time for deter