Online Edge Coloring: Sharp Thresholds

Abstract

Vizing's theorem guarantees that every graph with maximum degree $\hat{I}”$ admits an edge coloring using $\hat{I}”+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\hat{I}”-1$ colors. Over thirty years ago, Bar-Noy, Motwani, and Naor [IPL'92] proved that this guarantee is optimal among deterministic algorithms when $\hat{I}”=O(\log n)$, and among randomized algorithms when $\hat{I}”=O(\sqrt{\log n})$. While deterministic improvements seemed out of reach, they conjectured that for graphs with $\hat{I}”=\ddot{I}‰(\log n)$, randomized algorithms can achieve $(1+o(1))\hat{I}”$ edge coloring. This conjecture was recently resolved in the affirmative: a $(1+o(1))\hat{I}”$-coloring is achievable online using randomization for all graphs with $\hat{I}”=\ddot{I}‰(\log n)$ [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))\hat{I}”$-colorings for all $\hat{I}”=\ddot{I}‰(\log n)$. Second, we give a randomized algorithm achieving $(1+o(1))\hat{I}”$-colorings already when $\hat{I}”=\ddot{I}‰(\sqrt{\log n})$. Our results establish sharp thresholds for when greedy can be surpassed, and near-optimal guarantees can be achieved - matching the impossibility results of [BNMN IPL'92], both deterministically and randomly.

41 pages; to appear at FOCS'25