Abstract
Nearly thirty years ago, Bar-Noy, Motwani, and Naor [IPL'92] conjectured that an online $(1+o(1))\Delta$-edge-coloring algorithm exists for $n$-node graphs of maximum degree $\Delta=\omega(\log n)$. This conjecture has remained a significant open problem in the field of online algorithms. In this work, we resolve the conjecture in the affirmative for the random-order online model. Furthermore, we investigate edge coloring in the dynamic model with recourse. While previous state-of-the-art results achieved $(1+\epsilon)\Delta$-edge-coloring with $poly(\log n / \epsilon)$ recourse, we provide an algorithm that achieves the same color bound with $poly(1/\epsilon)$ recourse, effectively removing all dependence on the graph size $n$. Both results are derived from a common offline framework based on the Rödl Nibble Method, adapted for the constraints of online and dynamic environments.
Introduction
Edge coloring is a classic problem in combinatorial optimization: the goal is to assign colors to the edges of a graph such that no two incident edges share the same color. Vizing’s Theorem establishes that any graph can be edge-colored using at most $\Delta+1$ colors offline, where $\Delta$ is the maximum degree. However, in the online setting—where edges arrive sequentially and must be colored immediately—the problem becomes significantly more challenging.
A simple greedy approach uses $2\Delta-1$ colors, which is optimal for adversarial arrivals when $\Delta$ is small. However, for graphs with large maximum degrees ($\Delta = \omega(\log n)$), it has long been suspected that a much more efficient coloring is possible. This paper addresses this gap by studying two primary relaxations of the adversarial online model: the random-order online model and the dynamic model with recourse.
The Nibble Method in an Online Context
The technical foundation of our work is the Rödl Nibble Method, a probabilistic technique originally popularized in distributed computing. The method operates in discrete rounds to iteratively color the graph:
- Sampling: In each round, a small fraction ($\epsilon$) of currently uncolored edges is selected.
- Tentative Coloring: Each sampled edge independently chooses a color at random from its available palette (colors not already finalized by its neighbors).
- Conflict Resolution: If two incident edges select the same color, the assignment is discarded, and the edges remain uncolored for the next round. Otherwise, the color is finalized.
- Cleanup: After a sufficient number of rounds, the remaining uncolored edges are processed using a greedy algorithm.
Our contribution lies in adapting this offline, multi-round process to online constraints. In the random-order model, we demonstrate that the random arrival sequence of edges naturally mimics the sampling step of the Nibble method. To handle graphs with varying degrees, we utilize a "regularizing gadget"—a virtual expansion involving dummy nodes and edges—to make the graph appear near-regular to the algorithm.
Dynamic Coloring and Recourse
In the dynamic model, edges can be both added and deleted. To maintain a high-quality coloring, algorithms are permitted "recourse"—the ability to re-color a limited number of existing edges. Previous algorithms, such as those by Duan et al. [SODA'19], achieved a $(1+\epsilon)\Delta$-coloring but suffered from a recourse bound that scaled with the number of nodes ($poly(\log n)$).
By applying a distribution-matching technique to our Nibble-based framework, we ensure that the "ripples" caused by an edge update remain local. We prove that the expected recourse is a function of $\epsilon$ alone ($poly(1/\epsilon)$), marking the first time the dependence on $n$ has been eliminated in this context.
Key Results and Analysis
Random-Order Online Model
We settle the Bar-Noy et al. conjecture for the random-order model. For graphs where $\Delta = \omega(\log n)$, our algorithm produces a proper coloring using $\Delta + O(\Delta^\gamma \cdot \log^{1-\gamma} n)$ colors, which is $(1+o(1))\Delta$. We also provide a lower bound showing that if $\Delta = O(\sqrt{\log n})$, even random arrivals may require $2\Delta-2$ colors, suggesting that the $\omega(\log n)$ condition is likely necessary.
Dynamic Model with Recourse
We provide a dynamic algorithm maintaining a $(1+\epsilon)\Delta$-coloring with expected recourse of $poly(1/\epsilon)$. This result is achieved by modifying the standard Nibble method to sample edges independently rather than vertex-centrically, allowing for simpler concentration analysis via Hoeffding bounds.
Conclusion
By bridging the gap between distributed computing techniques and online algorithms, we resolve a long-standing conjecture in the random-order model and optimize recourse bounds in dynamic settings. Future work remains in the strictly adversarial online model, where the inability to "look ahead" at future samples makes the Nibble method difficult to apply directly. Additionally, developing versions of these algorithms that do not require prior knowledge of $\Delta$ remains an open challenge for practical streaming applications.
Summary updated