Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors

For any ∆, let k ∆ be the maximum integer k such that (k + 1)(k + 2) ⩽ ∆. We give a distributed LOCAL algorithm that, given an integer k < k ∆ , computes a valid ∆ -k-coloring if one exists. The algorithm runs in O(log 4 log n) rounds, which is within a polynomial factor of the Ω(log log n) lower bound, which already applies to the case k = 0. It is also best possible in the sense that if k ⩾ k ∆ , the problem requires Ω(n/∆) distributed rounds [Molloy, Reed, '14, Bamas, Esperet '19].

For ∆ at most polylogarithmic, the algorithm is an exponential improvement over the current state of the art of O(log 49/12 n) rounds. When ∆ ⩾ (log n) 50 , our algorithm achieves an even faster runtime of O(log * n) rounds.