Problem
Edge coloring
A proper $c$-edge coloring of a graph $G = (V, E)$ assigns each edge one of $c$ colors so that edges sharing an endpoint get different colors. Every edge is adjacent to at most $2\Delta - 2$ others, so coloring greedily never needs more than $2\Delta - 1$ colors; this is the classical symmetry-breaking variant, and the same as $(\Delta+1)$-vertex coloring the line graph $L(G)$.
With fewer colors the problem gets harder: at least $\Delta$ colors are always needed, and by Vizing's theorem $\Delta + 1$ colors always suffice. Palettes between these bounds, such as $3\Delta/2$ or $(1+\varepsilon)\Delta$, are studied in their own right.
Runtimes are given in rounds, in terms of the number of nodes $n$ and the maximum degree $\Delta$; $\varepsilon$, $\delta$ and $\gamma$ are fixed constants.