  Nearly three decades ago, Bar-Noy, Motwani and Naor showed that no online
edge-coloring algorithm can edge color a graph optimally. Indeed, their work,
titled "the greedy algorithm is optimal for on-line edge coloring", shows that
the competitive ratio of $2$ of the na\"ive greedy algorithm is best possible
online. However, their lower bound required bounded-degree graphs, of maximum
degree $\Delta = O(\log n)$, which prompted them to conjecture that better
bounds are possible for higher-degree graphs. While progress has been made
towards resolving this conjecture for restricted inputs and arrivals or for
random arrival orders, an answer for fully general \emph{adversarial} arrivals
remained elusive.
  We resolve this thirty-year-old conjecture in the affirmative, presenting a
$(1.9+o(1))$-competitive online edge coloring algorithm for general graphs of
degree $\Delta = \omega(\log n)$ under vertex arrivals. At the core of our
results, and of possible independent interest, is a new online algorithm which
rounds a fractional bipartite matching $x$ online under vertex arrivals,
guaranteeing that each edge $e$ is matched with probability $(1/2+c)\cdot x_e$,
for a constant $c>0.027$.
