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, Motwani and Naor showed over a quarter century ago 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 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 (e/e-1 - Omega(1)) Delta-edge-coloring algorithm exists. We then provide an optimal, (e/e-1 + o(1))Delta-edge-coloring algorithm for unknown Delta = omega(log n). To obtain our results, we study a nonstandard 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.