Coloring Fast Without Learning Your Neighbors' Colors
Magnús M. Halldórsson, Fabian Kühn, Yannic Maus, Alexandre Nolin · arXiv (Cornell University) · 2020
We give an improved randomized CONGEST algorithm for distance-$2$ coloring that uses $Δ^2+1$ colors and runs in $O(\log n)$ rounds, improving the recent $O(\log Δ\cdot \log n)$-round algorithm in [Halldórsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to $O(\log Δ) + 2^{O(\sqrt{\log\log n})}$.