Coloring Fast Without Learning Your Neighbors' Colors

Magnus M. Halldorsson, Fabian Kuhn, Yannic Maus +1

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)$-rou…