  Vizing's celebrated theorem asserts that any graph of maximum degree $\Delta$
admits an edge coloring using at most $\Delta+1$ colors. In contrast, Bar-Noy,
Naor and Motwani showed over a quarter century that the trivial greedy
algorithm, which uses $2\Delta-1$ colors, is optimal among online algorithms.
Their lower bound has a caveat, however: it only applies to low-degree graphs,
with $\Delta=O(\log n)$, and they conjectured the existence of online
algorithms using $\Delta(1+o(1))$ colors for $\Delta=\omega(\log n)$. Progress
towards resolving this conjecture was only made under stochastic arrivals
(Aggarwal et al., FOCS'03 and Bahmani et al., SODA'10).
  We resolve the above conjecture for \emph{adversarial} vertex arrivals in
bipartite graphs, for which we present a $(1+o(1))\Delta$-edge-coloring
algorithm for $\Delta=\omega(\log n)$ known a priori. Surprisingly, if $\Delta$
is not known ahead of time, we show that no $\big(\frac{e}{e-1} - \Omega(1)
\big) \Delta$-edge-coloring algorithm exists. We then provide an optimal,
$\big(\frac{e}{e-1}+o(1)\big)\Delta$-edge-coloring algorithm for unknown
$\Delta=\omega(\log n)$. Key to our results, and of possible independent
interest, is a novel fractional relaxation for edge coloring, for which we
present optimal fractional online algorithms and a near-lossless online
rounding scheme, yielding our optimal randomized algorithms.
