Vizings 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=omega(log n)$. Progress towards resolving this conjecture was only made under stochastic arrivals (Aggarwal et al., FOCS03 and Bahmani et al., SODA10). We resolve the above conjecture for emph{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 $big(frac{e}{e-1} - Omega(1) big) Delta$-edge-coloring algorithm exists. We then provide an optimal, $big(frac{e}{e-1}+o(1)big)Delta$-edge-coloring algorithm for unknown $Delta=omega(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.
Download