  Vizing's theorem states that every graph $G$ of maximum degree $\Delta$ can
be properly edge-colored using $\Delta + 1$ colors. The fastest currently known
$(\Delta+1)$-edge-coloring algorithm for general graphs is due to Sinnamon and
runs in time $O(m\sqrt{n})$, where $n :=|V(G)|$ and $m :=|E(G)|$. We
investigate the case when $\Delta$ is constant, i.e., $\Delta = O(1)$. In this
regime, the runtime of Sinnamon's algorithm is $O(n^{3/2})$, which can be
improved to $O(n \log n)$, as shown by Gabow, Nishizeki, Kariv, Leven, and
Terada. Here we give an algorithm whose running time is only $O(n)$, which is
obviously best possible. Prior to this work, no linear-time
$(\Delta+1)$-edge-coloring algorithm was known for any $\Delta \geq 4$. Using
some of the same ideas, we also develop new algorithms for
$(\Delta+1)$-edge-coloring in the $\mathsf{LOCAL}$ model of distributed
computation. Namely, when $\Delta$ is constant, we design a deterministic
$\mathsf{LOCAL}$ algorithm with running time $\tilde{O}(\log^5 n)$ and a
randomized $\mathsf{LOCAL}$ algorithm with running time $O(\log ^2 n)$.
Although our focus is on the constant $\Delta$ regime, our results remain
interesting for $\Delta$ up to $\log^{o(1)} n$, since the dependence of their
running time on $\Delta$ is polynomial. The key new ingredient in our
algorithms is a novel application of the entropy compression method.
