Advancements in Online Edge Coloring Algorithms

Abstract

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 $\mathrm{\Delta }$.

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))\mathrm{\Delta }$ colors) exhibit sharp threshold phenomena that match long-standing lower bounds, resolving and strengthening a conjecture of Bar-Noy, Motwani, and Naor [1].

First, while the conjecture posited the existence of a randomized algorithm achieving a $(1+o(1))\mathrm{\Delta }$-edge-coloring for maximum degree $\mathrm{\Delta }=\omega (\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 $\mathrm{\Delta }=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))\mathrm{\Delta }$-edge-coloring already for graphs with maximum degree $\mathrm{\Delta }=\omega (\sqrt{\log n})$. This establishes a sharp threshold for randomized algorithms, matching the lower bound in [1] for the $\mathrm{\Delta }=O(\sqrt{\log n})$ regime.

This is joint work with Joakim Blikstad, Radu Vintan, and David Wajc [2, 3].