Distributed Graph Coloring Made Easy
Distributed Graph Coloring Made Easy
In this article, we present a deterministic \(\mathsf {CONGEST}\) algorithm to compute an O ( k Δ)-vertex coloring in O (Δ / k )+log * n rounds, where Δ is the maximum degree of the network graph and k ≥ 1 can be freely chosen. The algorithm is extremely simple: …