  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(\log^5\log 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(\log\Delta + \log^6\log 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\"{i}ve folklore algorithm. For
large maximum degree $\Delta$, our algorithm hence is an exponential
improvement over the previous state of the art.

Data Structures and Algorithms;Distributed, Parallel, and Cluster Computing