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.

A proper edge coloring The three-dimensional cube graph, in which every node has degree three, with its edges colored by direction using three colors: the edges at every node have different colors.
The edges at every node have different colors. Here $\Delta = 3$ colors suffice; greedy coloring may use up to $2\Delta - 1 = 5$.