Online Edge Coloring: Sharp Thresholds

Vizing’s theorem guarantees that every graph with maximum degree Δ admits an edge coloring using Δ+1 colors. In online settings-where edges arrive one at a time and must be colored immediately-a simple greedy algorithm uses at most 2Δ−1 colors. Over thirty years ago, Bar-Noy, Motwani, and Naor [IPL’92] proved that this guarantee is optimal among deterministic algorithms when Δ=O(logn), and among randomized algorithms when Δ=O(logn−−−−√). While deterministic improvements seemed out of reach, they conjectured that for graphs with Δ=ω(logn), randomized algorithms can achieve (1+o(1))Δ edge coloring. This conjecture was recently resolved in the affirmative: a (1+o(1))Δ coloring is achievable online using randomization for all graphs with Δ=ω(logn) [BSVW STOC’24]. Our results go further, uncovering two findings not predicted by the original conjecture. First, we give a deterministic online algorithm achieving (1+o(1))Δ-colorings for all Δ=ω(logn). Second, we give a randomized algorithm achieving (1+o(1))Δ colorings already when Δ=ω(logn−−−−√). Our results establish sharp thresholds for when greedy can be surpassed, and nearoptimal guarantees can be achieved - matching the impossibility results of [BNMN IPL’92], both deterministically and randomly.