Overcoming Congestion in Distributed Coloring
Magnús M. Halldórsson, Alexandre Nolin, Tigran Tonoyan · 2022
We present a new technique to efficiently sample and communicate a large number of elements from a distributed sampling space. When used in the context of a recent Local algorithm for (degree +1)-list-coloring (D1LC), this allows us to solve D1LC in O(log5 logn) Congest rounds, and in only O(log* n) rounds when the graph has minimum degree Ω(log7 n), w.h.p.