Fast Coloring Despite Congested Relays

Maxime Flin, Magnús M. Halldórsson, Alexandre Nolin

We provide a $O({\log }^6\log n)$-round randomized algorithm for distance-2 coloring in CONGEST with ${\Delta }^2+1$ colors. For $\Delta \gg \mathrm{poly}\log n$, this improves exponentially…