Online Edge Coloring Is (Nearly) as Easy as Offline

Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc

Abstract

For decades, a significant gap existed between the theoretical limits of offline and online edge coloring. While offline graphs can be colored with $\Delta+1$ colors, online algorithms under adversarial arrivals were long stuck at a $1.58\Delta$ performance ratio. This paper resolves a 30-year-old conjecture by Bar-Noy, Motwani, and Naor, proving that for high-degree graphs ($\Delta = \omega(\log n)$), online edge coloring is possible using $(1 + o(1))\Delta$ colors. This is achieved through a novel "Natural Matching Algorithm" that adaptively handles vertex correlations using martingale analysis.

Introduction

Edge coloring is a cornerstone of combinatorial optimization. Given a graph $G$ with maximum degree $\Delta$, the goal is to assign colors to edges such that no two incident edges share a color. Vizing’s Theorem (1964) establishes that in the offline setting, where the entire graph is known, $\Delta$ or $\Delta+1$ colors suffice. However, many real-world applications—such as network routing or task scheduling—require decisions to be made "online." In the online edge coloring problem, edges arrive sequentially, and each must be assigned a color immediately and irrevocably.

The Adversarial Challenge

The most rigorous test for an online algorithm is the "adversarial" arrival model, where an opponent chooses the sequence of edges to maximize the algorithm's color usage. While simple greedy approaches use $2\Delta - 1$ colors, a 1992 conjecture by Bar-Noy, Motwani, and Naor suggested that for graphs with sufficiently large $\Delta$, an online algorithm should approach the offline efficiency of $(1+o(1))\Delta$. Despite significant progress in restricted models (like random-order arrivals), the adversarial case remained stalled at approximately $1.58\Delta$ for thirty years.

Methodology: The Natural Matching Algorithm

The authors bridge this gap by reducing the coloring problem to a matching problem. There is a known reduction where if an algorithm can match an arriving edge with probability $1/((1+\epsilon)\Delta)$, it can be transformed into an edge coloring algorithm using $(1+\epsilon)\Delta$ colors.

The breakthrough lies in the Natural Matching Algorithm. In previous attempts, the primary obstacle was "correlation": the probability of a vertex $u$ being free is not independent of the probability of vertex $v$ being free. Most algorithms failed because they could not account for these complex dependencies. The authors' approach scales the matching probability based on the actually observed state of the graph during execution, rather than relying on static theoretical averages.

To prove the algorithm's efficacy, the authors utilize Martingale theory and Freedman’s Inequality. By treating the probability of a vertex remaining available as a martingale, they demonstrate that the "observed variance" of the matching process remains low. This concentration of measure ensures that the algorithm does not deviate significantly from its intended path, allowing it to maintain a high matching probability even as the graph grows.

Key Results and Implications

The paper provides a definitive resolution to the 1992 conjecture. As a theoretical contribution, these results apply to all possible graphs under the adversarial model without the need for empirical datasets. Key findings include:

  • Conjecture Resolution: Proving $(1 + o(1))\Delta$ coloring is achievable for $\Delta = \omega(\log n)$ under adversarial arrivals.
  • Quantitative Bounds: Specifically, the authors show a coloring using $\Delta + O(\Delta^{3/4} \log^{1/2} \Delta + \Delta^{2/3} \log^{1/3} n)$ colors.
  • Breaking the 1.58 Barrier: By using the history of the algorithm to set probabilities, the authors pushed past the $e/(e-1) \approx 1.58$ barrier inherent in simpler independent sampling methods.
  • Algorithmic Versatility: The technique extends to List Edge Coloring (where edges have specific palettes) and Local Edge Coloring (where color counts depend on local vertex degrees).
  • Online Rounding: The work introduces the first $(1+o(1))$-approximate online rounding algorithm for fractional matchings in general graphs.

Limitations and Future Work

While the paper closes a major theoretical gap, several challenges remain:

  1. The Low-Degree Gap: The results require $\Delta = \omega(\log n)$. For graphs with very small maximum degrees, online algorithms are still fundamentally limited and cannot reach the $(1+o(1))\Delta$ bound.
  2. Tightening the Slack: The current "slack" term is $O(\Delta^{3/4})$. Lower bounds suggest $O(\sqrt{\Delta})$ might be the best possible; closing this gap remains an open problem.
  3. Unknown Maximum Degree: When $\Delta$ is unknown to the algorithm, the performance is currently $1.777\Delta$, which is still above the known lower bound of $1.606\Delta$.

Summary updated

BibTeX
@inproceedings{blikstad2025online,
  author = {Joakim Blikstad and Ola Svensson and Radu Vintan and David Wajc},
  title = {{Online Edge Coloring Is (Nearly) as Easy as Offline}},
  booktitle = {SIAM},
  year = {2025},
  doi = {10.1137/24m1689788},
}
Figure