Online Edge Coloring: Sharp Thresholds

Vizing’s theorem guarantees that every graph with maximum degree $\Delta$ admits an edge coloring using $\Delta+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 \Delta-1$ colors. Over thirty years ago, Bar-Noy, Motwani, and Naor [IPL’92] proved that this guarantee is optimal among deterministic algorithms when $\Delta=O(\log n)$, and among randomized algorithms when $\Delta=O(\sqrt{\log n})$. While deterministic improvements seemed out of reach, they conjectured that for graphs with $\Delta=\omega(\log n)$, randomized algorithms can achieve $(1+o(1)) \Delta$ edge coloring. This conjecture was recently resolved in the affirmative: a $(1+o(1)) \Delta$ coloring is achievable online using randomization for all graphs with $\Delta=\omega(\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)) \Delta$-colorings for all $\Delta=\omega(\log n)$. Second, we give a randomized algorithm achieving $(1+o(1)) \Delta$ colorings already when $\Delta=\omega(\sqrt{\log n})$. 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.

Authors

• Joakim Blikstad
• Ola Svensson
• Radu Vintan
• David Wajc

Keywords

• Greedy algorithms
• Computer science
• Color
• Prediction algorithms
• Edge Coloring
• Sharp Threshold
• Deterministic
• Conjecture
• Maximum Degree
• Online Algorithm
• High Probability
• Lower Bound
• Upper Bound
• Step Size
• State Lines
• Proof Of Result
• Proof Of The Lemma
• Random Choice
• Overview Of Techniques
• General Version
• Small Step Size
• Lemma States
• Algorithm Ends
• Incident Edges
• Potential Edge
• online algorithms
• graph algorithms
• randomized algorithms
• martingales