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$.