Coloring Fast Without Learning Your Neighbors' Colors

Abstract

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 [Halldórsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to $O(\log \Delta )+2^{O(\sqrt{\log \log n})}$.