Problem

Vertex coloring

A proper $c$-coloring of a graph $G = (V, E)$ assigns each node one of $c$ colors so that adjacent nodes get different colors. Coloring greedily, node by node, never needs more than $\Delta + 1$ colors, so $(\Delta+1)$-coloring is the classical symmetry-breaking problem.

With fewer colors the problem gets harder: by Brooks' theorem, every graph with $\Delta \geq 3$ that contains no $(\Delta+1)$-clique can be $\Delta$-colored. In the list variant each node $v$ picks its color from its own list of $\deg(v) + 1$ (or $\Delta + 1$) colors.

Runtimes are given in rounds, in terms of the number of nodes $n$ and the maximum degree $\Delta$.

A proper vertex coloring A graph with eleven nodes and maximum degree five, properly colored with three colors: no edge joins two nodes of the same color.
No edge joins two nodes of the same color. This graph has maximum degree $\Delta = 5$, but three colors suffice.