Improved distributed Δ -coloring.

We present a randomized distributed algorithm that computes a Δ -coloring in any non-complete graph with maximum degree Δ ≥ 4 in O ( log Δ ) + 2 O ( log log n ) rounds, as well as a randomized algorithm that computes a Δ -coloring in O ( ( log log n ) 2 ) rounds when Δ ∈ [ 3 , O ( 1 ) ] . Both these algorithms improve on an O ( log 3 n / log Δ ) -round algorithm of Panconesi and Srinivasan (STOC'93), which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an Ω ( log log n ) round lower bound of Brandt et al. (STOC'16).