Tight Bounds for Online Edge Coloring

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 2Delta-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=ω(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 adversarial vertex arrivals in bipartite graphs, for which we present a (1+o(1))Delta-edge-coloring algorithm for Delta=ω(log n) known a priori. Surprisingly, if Delta is not known ahead of time, we show that no big(fracee-1 - Omega(1) big) Delta-edge-coloring algorithm exists. We then provide an optimal, big(fracee-1+o(1)big)Delta-edge-coloring algorithm for unknown Delta=ω(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.