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 naive 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$.
Download