  The complexity of distributed edge coloring depends heavily on the palette
size as a function of the maximum degree $\Delta$. In this paper we explore the
complexity of edge coloring in the LOCAL model in different palette size
regimes.
  1. We simplify the \emph{round elimination} technique of Brandt et al. and
prove that $(2\Delta-2)$-edge coloring requires $\Omega(\log_\Delta \log n)$
time w.h.p. and $\Omega(\log_\Delta n)$ time deterministically, even on trees.
The simplified technique is based on two ideas: the notion of an irregular
running time and some general observations that transform weak lower bounds
into stronger ones.
  2. We give a randomized edge coloring algorithm that can use palette sizes as
small as $\Delta + \tilde{O}(\sqrt{\Delta})$, which is a natural barrier for
randomized approaches. The running time of the algorithm is at most
$O(\log\Delta \cdot T_{LLL})$, where $T_{LLL}$ is the complexity of a
permissive version of the constructive Lovasz local lemma.
  3. We develop a new distributed Lovasz local lemma algorithm for
tree-structured dependency graphs, which leads to a $(1+\epsilon)\Delta$-edge
coloring algorithm for trees running in $O(\log\log n)$ time. This algorithm
arises from two new results: a deterministic $O(\log n)$-time LLL algorithm for
tree-structured instances, and a randomized $O(\log\log n)$-time graph
shattering method for breaking the dependency graph into independent $O(\log
n)$-size LLL instances.
  4. A natural approach to computing $(\Delta+1)$-edge colorings (Vizing's
theorem) is to extend partial colorings by iteratively re-coloring parts of the
graph. We prove that this approach may be viable, but in the worst case
requires recoloring subgraphs of diameter $\Omega(\Delta\log n)$. This stands
in contrast to distributed algorithms for Brooks' theorem, which exploit the
existence of $O(\log_\Delta n)$-length augmenting paths.
