We study online edge coloring, where edges of an n-vertex graph arrive sequentially and must be colored irrevocably so that adjacent edges receive different colors. The goal is to use as few colors as possible as a function of the maximum degree Δ. This talk surveys recent progress that achieves near-optimal guarantees by leveraging martingale concentration arguments. Specifically, we show that near-optimal colorings (using (1+o (1) ) Δ colors) exhibit sharp threshold phenomena that match long-standing lower bounds, resolving and strengthening a conjecture of Bar‑Noy, Motwani, and Naor Bar-Noy et al. , 1992. First, while the conjecture posited the existence of a randomized algorithm achieving a (1+o (1) ) Δ-edge-coloring for maximum degree Δ = ω (log n), we present a deterministic online algorithm that achieves this guarantee in the same regime. This result matches the known impossibility result for deterministic algorithms when Δ = O (log n), establishing a sharp threshold. Second, improving the conditions under which near-optimal coloring is known to be possible with randomness, we present a randomized online algorithm achieving a (1+o (1) ) Δ-edge-coloring already for graphs with maximum degree Δ = ω (√log n). This establishes a sharp threshold for randomized algorithms, matching the lower bound in Bar-Noy et al. , 1992 for the Δ = O (√log n) regime. This is joint work with Joakim Blikstad, Radu Vintan, and David Wajc Joakim Blikstad et al. , 2024; Joakim Blikstad et al. , 2025.
Ola Svensson (Thu,) studied this question.