# Efficient Randomized Distributed Coloring in CONGEST

arXiv: https://arxiv.org/abs/2012.14169 · HTML: https://mlsanity.com/paper/2012.14169/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Dec 2020.

## Built on by (most cited first, 2 of 2)

- [Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions](https://mlsanity.com/paper/2109.14528/) (2021)
- [Collaborative Learning in General Graphs with Limited Memorization: Complexity, Learnability, and Reliability](https://mlsanity.com/paper/2201.12482/) (2022)

## Abstract (arXiv)

Distributed vertex coloring is one of the classic problems and probably also the most widely studied problems in the area of distributed graph algorithms. We present a new randomized distributed vertex coloring algorithm for the standard CONGEST model, where the network is modeled as an n-node graph G, and where the nodes of G operate in synchronous communication rounds in which they can exchange O(log n)-bit messages over all the edges of G. For graphs with maximum degree Delta, we show that the (Delta+1)-list coloring problem (and therefore also the standard (Delta+1)-coloring problem) can be solved in O(log5log n) rounds. Previously such a result was only known for the significantly more powerful LOCAL model, where in each round, neighboring nodes can exchange messages of arbitrary size. The best previous (Delta+1)-coloring algorithm in the CONGEST model had a running time of O(logDelta + log6log n) rounds. As a function of n alone, the best previous algorithm therefore had a round complexity of O(log n), which is a bound that can also be achieved by a na"ive folklore algorithm. For large maximum degree Delta, our algorithm hence is an exponential improvement over the previous state of the art.