Coloring Fast Without Learning Your Neighbors Colors

We give an improved randomized CONGEST algorithm for distance-$2$ coloring that uses $Delta^2+1$ colors and runs in $O(log n)$ rounds, improving the recent $O(log Delta cdot log n)$-round algorithm in [Halldorsson, Kuhn, Maus; PODC 20]. We then improve the time complexity to $O(log Delta) + 2^{O(sqrt{loglog n})}$.