  Vizing's celebrated theorem states that every simple graph with maximum
degree $\Delta$ admits a $(\Delta+1)$ edge coloring which can be found in $O(m
\cdot n)$ time on $n$-vertex $m$-edge graphs. This is just one color more than
the trivial lower bound of $\Delta$ colors needed in any proper edge coloring.
After a series of simplifications and variations, this running time was
eventually improved by Gabow, Nishizeki, Kariv, Leven, and Terada in 1985 to
$O(m\sqrt{n\log{n}})$ time. This has effectively remained the state-of-the-art
modulo an $O(\sqrt{\log{n}})$-factor improvement by Sinnamon in 2019.
  As our main result, we present a novel randomized algorithm that computes a
$\Delta+O(\log{n})$ coloring of any given simple graph in $O(m\log{\Delta})$
expected time; in other words, a near-linear time randomized algorithm for a
``near''-Vizing's coloring.
  As a corollary of this algorithm, we also obtain the following results:
  * A randomized algorithm for $(\Delta+1)$ edge coloring in $O(n^2\log{n})$
expected time. This is near-linear in the input size for dense graphs and
presents the first polynomial time improvement over the longstanding bounds of
Gabow et.al. for Vizing's theorem in almost four decades.
  * A randomized algorithm for $(1+\varepsilon) \Delta$ edge coloring in
$O(m\log{(1/\varepsilon)})$ expected time for any $\varepsilon =
\omega(\log{n}/\Delta)$. The dependence on $\varepsilon$ exponentially improves
upon a series of recent results that obtain algorithms with runtime of
$\Omega(m/\varepsilon)$ for this problem.
