Edge coloring assigns a color to every link of a network so that no two links sharing an endpoint get the same color. Each color class is a set of links that can act at the same moment, so a coloring is a schedule: color $k$ means "time slot $k$." The best fast algorithms for edge coloring in streaming and online settings use the nibble method. In each round, every uncolored edge tentatively picks a random available color, and only conflict-free picks are kept. Because only a small fraction of edges gets colored per round, the remaining problem stays well behaved and close to its expected state. These algorithms have a catch, though: they measure everything against one global maximum degree $\Delta$, which must be known in advance and must be large. Real networks are heavy-tailed. They have a few hubs with enormous degree and millions of low-degree vertices. A schedule of length about $\Delta$ is correct on such a graph, but it is useless for the low-degree majority. An edge between two degree-3 vertices has no reason to wait until slot $10^5$ just because some hub elsewhere has degree $10^5$.
This note proposes a degree-local guarantee for online edge coloring in which edges arrive in random order. Every edge $e=uv$ should receive a color of at most $(1+\epsilon)\max(d_u,d_v)$, where $d_u$ is the final degree of $u$, and the algorithm should never be told $\Delta$ or any degree in advance. The mechanism is a nibble with two changes. First, each edge estimates its endpoints' degrees from the arrivals seen so far, which random order makes accurate. Second, an edge prefers colors that lie above the "home range" $[1,(1+\epsilon)d]$ of its lower-degree endpoint. Hub edges are therefore pushed into slots that low-degree vertices never need.
Core Claim
Online greedy first-fit already achieves a local guarantee of factor two in any arrival order. Edge $uv$ sees at most $(d_u-1)+(d_v-1)$ blocked colors, so it gets a color of at most $2\max(d_u,d_v)-1$. The real question is therefore whether the factor 2 can be driven to $1+\epsilon$ locally, with no knowledge of degrees. This is the degree-local analogue of the global $(1+o(1))\Delta$ result that Online Edge Coloring Algorithms via the Nibble Method proved for random-order arrivals when $\Delta=\omega(\log n)$.
Our claim is a conditional one. Under random order, with high probability every edge with $\max(d_u,d_v)\ge C\log n$ receives a color of at most $(1+o(1))\max(d_u,d_v)$. The remaining low-degree edges fall back to greedy and its factor-two bound. We state this honestly as an exception, because nibble concentration fails at small degrees, as the file's summary of nibble limitations notes.
Relation to Prior Work
Three papers motivate the problem. Online Edge Coloring Algorithms via the Nibble Method supplies the round-based online nibble that we reuse. Its retention probabilities and its guarantee are both scaled to a single global $\Delta$, and that global scaling is exactly what we remove. Nibbling at Long Cycles maintains a dynamic $(1+\epsilon)\Delta$ edge coloring in constant update time, again against a fixed $\Delta$. Constant-Time Dynamic (Δ+1)-Coloring handles vertex coloring and explicitly leaves open graphs whose $\Delta$ "can change significantly and rapidly." Our online setting, where the maximum degree grows as hubs accumulate edges, is a clean instance of that open case, although we do not attack the dynamic deletion setting.
Two papers supply the local-degree template for vertex coloring. Palette Sparsification Beyond (Δ+1) Vertex Coloring shows that vertices can sample palettes according to $\deg(v)+1$. It needs a three-way decomposition, including "uneven" vertices whose many high-degree neighbors drain their colors. We take from it the lesson that hubs deplete low-degree neighborhoods. Our range-avoiding color preference is the edge-coloring answer to that depletion, and it replaces a structural case analysis with a local sampling rule. Simple Sublinear Algorithms for (Δ+1) Vertex Coloring via Asymmetric Palette Sparsification shows that asymmetric, rank-dependent sampling can remove a decomposition. However, it still draws from a global $(\Delta+1)$ palette.
One paper constrains how we frame the result. Vizing's Theorem in Near-Linear Time colors offline with $\Delta+1$ colors in $O(m\log\Delta)$ time. On a heavy-tailed graph that gives a small palette overall but no per-edge locality. We therefore do not compete on total colors, and we use this paper as an offline reference.
We also rejected one attractive gap in the file: sublinear-time $(\deg+1)$ vertex coloring with query cost near $n\bar d$, where $\bar d$ is the average degree. Reading the whole graph and running greedy already costs $O(m)=O(n\bar d)$, so that target is met trivially on sparse graphs.
Research Program
The algorithm has three pieces.
The first piece is degree estimation. In a random-order stream, at time fraction $t$, the observed degree $\hat d_v(t)$ satisfies $\hat d_v(t)/t\approx d_v$ within a factor $1\pm O(\sqrt{\log n/(t d_v)})$, by concentration for sampling without replacement. Each arriving edge uses these estimates. A small $t$-dependent inflation keeps them from underestimating.
The second piece is the nibble. It follows the round structure of the global algorithm, with one change: edge $uv$ with estimated degrees $m\le M$ draws its tentative color from $((1+\epsilon)m,(1+\epsilon)M]$. It draws from the full range $[1,(1+\epsilon)M]$ only when the preferred band is exhausted at the hub.
The third piece is the greedy fallback for edges whose larger degree is below $C\log n$.
The analysis goal is a vertex-local version of the palette-concentration invariant from the global nibble. For every vertex $v$ and every threshold $k$, the number of free colors below $k$ at $v$ should track its expectation. The new difficulty is interference between degree scales: a hub edge that takes a low color consumes space in its partner's home range. We will first prove the static version, a random permutation fed to the same process, before handling estimation error. As an independent milestone, we will establish whether a $(1+\epsilon)\max(d_u,d_v)$ local coloring exists offline for large degrees.
Baselines
The naive reference is online greedy first-fit in arrival order. It needs no parameters, and its per-edge ratio $\mathrm{color}(e)/\max(d_u,d_v)$ is provably at most 2. Empirically it may be much lower on real graphs, which makes it the most dangerous competitor.
The strongest existing nibble is the global random-order algorithm of Online Edge Coloring Algorithms via the Nibble Method. We will run it with the true $\Delta$ given as an oracle, which advantages it. We expect its total palette to be the best of all methods. We also expect its local ratio for low-degree edges to be near $\Delta/\max(d_u,d_v)$.
A doubling-trick variant guesses $\Delta$, restarts with a fresh color block whenever the guess is exceeded, and runs the global nibble inside each block.
For offline references, we use a Vizing-type $(\Delta+1)$ coloring in the spirit of Vizing's Theorem in Near-Linear Time, plus offline greedy in decreasing order of $\max(d_u,d_v)$.
Two ablations isolate the key ingredients. The first removes the range-avoiding preference, so edges sample uniformly from $[1,(1+\epsilon)M]$. The second replaces estimated degrees with true degrees supplied by an oracle, which separates the cost of not knowing degrees from the cost of locality.
All methods see the same random-order streams, with ten seeds per graph. Each nibble variant gets the same grid over $\epsilon$ and round length, and we report the best setting per method.
No reported result was found on Lacuna for per-edge local color ratios, or for any edge-coloring quality metric, on SNAP or OGB graphs. The comparison numbers will therefore all be produced in this study. Beating greedy means a lower 99th-percentile local ratio on edges with $\max(d_u,d_v)\ge C\log n$, and a lower mean color, at matched runtime within a constant factor.
Why not just…?
Why not just use greedy first-fit, which is already local? This is the real threat. Greedy's factor-two bound is worst-case, and random-order greedy on power-law graphs may sit close to 1 in practice. The experiments measure exactly this. If greedy's high-degree local ratio is already within a few percent of $1+\epsilon$ on SNAP graphs, the empirical case collapses and the contribution reduces to the worst-case guarantee. We would then report it as such. The synthetic adversarial-but-random-order family below, where many hubs share medium-degree neighbors, is designed to show where greedy's ratio actually rises.
Why not just run the global nibble with a guessed $\Delta$, or with doubling? Global scaling gives every edge a color that is uniform over roughly $[1,\Delta]$. Low-degree edges therefore get ratios near $\Delta/d$, which the file's discussion of palette-waste under heavy-tailed degrees predicts. Doubling fixes the unknown $\Delta$ but not the locality. It also adds up to a factor of about 2 in total colors from the geometric series of blocks. Both variants are baselines, so their local-ratio curves will show this directly.
Why not just truncate hubs and color their edges from a separate palette? Reserving fresh colors for hub edges inflates the palette by the hubs' total degree. The file notes that this breaks every near-optimal bound, and Palette Sparsification Beyond (Δ+1) Vertex Coloring found that uneven vertices cannot be handled by degree peeling. We include a truncation baseline with threshold $\tau=\sqrt n$ to confirm this on real hub structure.
Proposed Experiments
The real graphs come from the SNAP collection described in SNAP: A General-Purpose Network Analysis and Graph-Mining Library: LiveJournal (69M edges), Twitter2010 (1.5B edges), and a road network that serves as a near-bounded-degree control. We add ogbn-papers100M from Open Graph Benchmark, which has 111M nodes and 1.6B edges. For synthetic graphs, we sweep the power-law exponent from 2.1 to 3.5 using A random growth model with any real or theoretical degree distribution, and we include random regular graphs, where local and global guarantees coincide.
The metrics are the distribution of the per-edge ratio $\mathrm{color}(e)/\max(d_u,d_v)$, its maximum and 99th percentile, the mean color (the average schedule latency), total colors used relative to $\Delta$, and wall-clock time.
Two checks are decisive. The first tests the theory. Binning edges by $\max(d_u,d_v)$, the worst ratio of our method should approach $1+\epsilon$ as the bin degree grows past $C\log n$. The global nibble's ratio should grow like $\Delta/\max(d_u,d_v)$, and greedy's should stay flat at some value we have to measure.
The second tests the proposed mechanism. The range-avoiding ablation should show that low-degree vertices adjacent to hubs, the edge analogue of "uneven" vertices, are where uniform sampling fails. The degree-oracle ablation should show that estimation costs only in early rounds.
Finally, we feed the same graphs in adversarial order to check the random-order assumption: our guarantee should degrade there while greedy's does not.
References
- Online Edge Coloring Algorithms via the Nibble Method
- Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time
- Constant-Time Dynamic (Δ+1)-Coloring
- Palette Sparsification Beyond (Δ+1) Vertex Coloring
- Simple Sublinear Algorithms for (Δ+1) Vertex Coloring via Asymmetric Palette Sparsification
- Vizing's Theorem in Near-Linear Time
- SNAP: A General Purpose Network Analysis and Graph Mining Library
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- A random growth model with any real or theoretical degree distribution