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, Motwani and Naor showed over a quarter century ago the trivial greedy algorithm, which uses 2Δ-1 colors, is optimal among online algorithms. Their lower bound has caveat, however: it only applies to low-degree graphs, with Δ=O(log n), they conjectured existence algorithms Δ(1+o(1)) colors for Δ=ω(log n). Progress towards resolving this conjecture was made under stochastic arrivals (Aggarwal et al., FOCS'03 Bahmani SODA'10). We resolve above adversarial vertex in bipartite we present (1+o(1))Δ-edge-coloring algorithm n) known priori. Surprisingly, if not ahead time, show no (e/e-1 - Ω(1)) Δ-edge-coloring exists. then provide optimal, (e/e-1+o(1)) unknown To obtain our results, study nonstandard fractional relaxation coloring, near-lossless rounding scheme, yielding randomized