Tight Bounds for Online Edge Coloring

Vizing's celebrated theorem asserts that any graph of maximum degree $Δ$ admits an edge coloring using at most $Δ+1$ colors. In contrast, Bar-Noy, Naor and Motwani showed over a quarter century that the trivial greedy algorithm, which uses $2Δ-1$ colors, is optimal among online algorithms. Their lower bound has a caveat, however: it only applies to low-degree graphs, with $Δ=O(\log n)$, and they conjectured the existence of online algorithms using $Δ(1+o(1))$ colors for $Δ=ω(\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))Δ$-edge-coloring algorithm for $Δ=ω(\log n)$ known a priori. Surprisingly, if $Δ$ is not known ahead of time, we show that no $\big(\frac{e}{e-1} - Ω(1) \big) Δ$-edge-coloring algorithm exists. We then provide an optimal, $\big(\frac{e}{e-1}+o(1)\big)Δ$-edge-coloring algorithm for unknown $Δ=ω(\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.