Distributed $(\Delta +1)$-Coloring in Sublogarithmic Rounds

David G. Harris, Johannes Schneider, Hsin-Hao Su

We give a new randomized distributed algorithm for $(\Delta +1)$-coloring in the LOCAL model, running in $O(\sqrt{\log \Delta })+2^{O(\sqrt{\log \log n})}$ rounds in a graph of maximum degree…