Problem
Network decomposition
A $(C, D)$-network decomposition of a graph $G = (V, E)$ partitions the nodes into clusters of diameter at most $D$ and colors the clusters with $C$ colors so that adjacent clusters get different colors. The diameter is weak if it is measured in $G$ and strong if it is measured inside the cluster.
Every graph has a decomposition with $C = \mathcal{O}(\log n)$ and $D = \mathcal{O}(\log n)$. Given one, MIS, $(\Delta+1)$-coloring and many other problems can be solved in $\mathcal{O}(C \cdot D)$ rounds by going through the colors one by one (see the reductions).
Runtimes are given in rounds, in terms of the number of nodes $n$.