  Vizing's theorem states that any $n$-vertex $m$-edge graph of maximum degree
$\Delta$ can be {\em edge colored} using at most $\Delta + 1$ different colors
[Diskret.~Analiz, '64]. Vizing's original proof is algorithmic and shows that
such an edge coloring can be found in $\tilde{O}(mn)$ time. This was
subsequently improved to $\tilde O(m\sqrt{n})$, independently by Arjomandi
[1982] and by Gabow et al.~[1985].
  In this paper we present an algorithm that computes such an edge coloring in
$\tilde O(mn^{1/3})$ time, giving the first polynomial improvement for this
fundamental problem in over 40 years.
