Abstract 1 Introduction 2 Preliminaries 3 Randomized 𝚫𝟒/𝟑+ϵ Edge Coloring References

Improved Streaming Edge Coloring

Shiri Chechik Tel Aviv University, Israel Hongyi Chen State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory, Nanjing University, China Tianyi Zhang ORCID ETH Zürich, Switzerland
Abstract

Given a graph, an edge coloring assigns colors to edges so that no pairs of adjacent edges share the same color. We are interested in edge coloring algorithms under the W-streaming model. In this model, the algorithm does not have enough memory to hold the entire graph, so the edges of the input graph are read from a data stream one by one in an unknown order, and the algorithm needs to print a valid edge coloring in an output stream. The performance of the algorithm is measured by the amount of space and the number of different colors it uses.

This streaming edge coloring problem has been studied by several works in recent years. When the input graph contains n vertices and has maximum vertex degree Δ, it is known that in the W-streaming model, an O(Δ2)-edge coloring can be computed deterministically with O~(n) space [Ansari, Saneian, and Zarrabi-Zadeh, 2022], or an O(Δ1.5)-edge coloring can be computed by a O~(n)-space randomized algorithm [Behnezhad, Saneian, 2024] [Chechik, Mukhtar, Zhang, 2024].

In this paper, we achieve polynomial improvement over previous results. Specifically, we show how to improve the number of colors to O~(Δ4/3+ϵ) using space O~(n) deterministically, for any constant ϵ>0. This is the first deterministic result that bypasses the quadratic bound on the number of colors while using near-linear space.

Keywords and phrases:
edge coloring, streaming
Category:
Track A: Algorithms, Complexity and Games
Funding:
Shiri Chechik: European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 803118 UncertainENV).
Tianyi Zhang: Starting grant “A New Paradigm for Flow and Cut Algorithms” (no. TMSGI2_218022) of the Swiss National Science Foundation.
Copyright and License:
[Uncaptioned image] © Shiri Chechik, Hongyi Chen, and Tianyi Zhang; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation Streaming, sublinear and near linear time algorithms
; Theory of computation Graph algorithms analysis
Related Version:
Full Version: https://arxiv.org/abs/2504.16470 [18]
Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

1 Introduction

Let G=(V,E) be an undirected graph on n vertices with maximum vertex degree Δ. An edge coloring of G is an assignment of colors to edges in E such that no pairs of adjacent edges share the same color, and the basic objective is to understand the smallest possible number of colors that are needed in any edge coloring, which is called the edge-chromatic number of G. It is clear that the total number of colors should be at least Δ, and a simple greedy algorithm can always find an edge coloring using 2Δ1 colors. By the celebrated Vizing’s theorem [43] and Shannon’s theorem [40], (Δ+1)-edge coloring and 3Δ/2-edge coloring always exist in simple and multi-graphs respectively, and these two upper bounds are tight in some hard cases.

The edge coloring problem has been studied widely from the algorithmic perspective. There have been efficient algorithms for finding good edge coloring in various computational models, including sequential [2, 30, 41, 3, 9, 12, 4], dynamic [6, 10, 26, 21, 11, 20], online [22, 13, 38, 36, 14, 15, 27], and distributed [37, 28, 29, 31, 5, 16, 8, 21, 24] models. In this paper, we are particularly interested in computing edge coloring under the streaming model where we assume the input graph does not fit in the memory of the algorithm and can only be accessed via one pass over a stream of all edges in the graph. Since the output of edge coloring is as large as the graph size, the algorithm cannot store it in its memory. To address this limitation, the streaming model is augmented with an output stream in which the algorithm can write its answers during execution, and this augmented streaming model is thus called the W-streaming model.

Edge coloring in the W-streaming model was first studied in [7], and improved by follow-up works [17, 1] which led to a deterministic edge coloring algorithm using O(Δ2) colors and O(n) space, or O(Δ2/s) colors and O(ns) space as a general trade-off. In [32], the authors improved the trade-off to O(Δ2/s) colors and 111O~(f) hides logf factors.O~(ns) memory, yet it does not break the quadratic bound in the most natural O~(n) memory regime; this algorithm is randomized but can be derandomized in exponential time. The quadratic upper bound of colors was subsequently bypassed in [39, 19] where it was shown that an O(Δ1.5)-edge coloring can be computed by a randomized algorithm using O~(n) space. Furthermore, in [39] the authors obtained a general trade-off of O(Δ1.5/s+Δ) colors and O~(ns) space which is an improvement over [32].

1.1 Our Results

In this paper, we focus on the basic O~(n)-memory setting and improve the recent Δ1.5 randomized upper bound to Δ4/3+ϵ.

Theorem 1.

Given a simple graph G=(V,E) on n vertices with maximum vertex degree Δ, for any constant ϵ>0, there is a randomized W-streaming algorithm that outputs a proper edge coloring of G using O((logΔ)O(1/ϵ)n) space and O((logΔ)O(1/ϵ)Δ4/3+ϵ) different colors; both upper bounds hold in expectation.

Furthermore, we also show that our algorithm can be derandomized using bipartite expanders based on error correcting codes at the cost of slightly worse bounds, as stated below. The deterministic algorithm and proof can be found in the full version [18].

Theorem 2.

Given a simple graph G=(V,E) on n vertices with maximum vertex degree Δ, for any constant ϵ>0, there is a deterministic W-streaming algorithm that outputs a proper edge coloring of G using O((logΔ)O(1/ϵ)(1/ϵ)O(1/ϵ3)Δ4/3+ϵ) colors and O(n(logΔ)O(1/ϵ4)) space.

1.2 Technical Overview

Previous Approaches

Using a deterministic general-to-bipartite reduction from [32], we can assume the input graph G=(LR,E) is bipartite. Also, it suffices to color only a constant fraction of all edges in G, because we can recurse on the rest 1Ω(1) fraction of G which only incurs an extra factor of O(logΔ) on the total number of different colors.

Let us begin by recapping the randomized O~(Δ1.5)-edge coloring from [39]. Since the algorithm has O~(n) bits of memory, we can assume that input graph is read from stream in batches of size Θ(n). If the subgraph formed by every batch has maximum degree at most Δ1/2, then we can allocate O(Δ1/2) new colors for each batch, using O(Δ1.5) colors in total. Thus, the main challenge arises when some batches contain subgraphs with maximum degree exceeding Δ1/2.

To simplify the problem, let us assume that in each batch of O(n) edges, every vertex in R has degree d>Δ1/2. To assign colors to edges, organize a table of colors of size Δ×(Δ/d), represented as a matrix C[i,j] with indices 1iΔ and 1jΔ/d. Then, for every vertex uL, draw a random shift ru uniformly at random from [Δ]. During the algorithm, each vertex uL keeps a counter cu of its degree in the stream so far, and each vertex vR keeps a counter bv of the number of batches in which it has appeared so far. Then, to color a single batch, for edge (u,v), the algorithm tentatively assigns the color C[ru+cu,bv] (indices are under modulo Δ).

Clearly, edges incident on the same vertex uL receive different colors, because the counter cu is incremented for each edge (u,v); also edges incident on the same vertex vR but arriving in different batches are different, because the values of counter bv are different. Randomization ensures that edges incident on vR within the same batch receive mostly different colors from the same column in C[,bv]. Consider all the d neighbors of v in a single batch u1,u2,,ud. Since all the random shifts rui are independent and all the counters cui are deterministic (they only depend on the input stream), with high probability, most row indices (rui+cui)modΔ will be different.

Bypassing the 𝚫1.5 Bound

To better understand the bottleneck in the approach of [39], consider the following case. If every batch forms a regular subgraph with uniform degree d, then we can reduce the size of the color table from Δ×(Δ/d) to (Δ/d)×(Δ/d), since each vertex uL could only appear in Δ/d different batches. So the main difficult case is when the batches are subgraphs of unbalanced degrees. As an extreme example, consider when vertices in L have degree 1, while the vertices in R have degree d. For the rest, our main focus will be on this extreme case, and show how to obtain a Δ1+ϵ-edge coloring which is almost optimal.

The flavor of our approach is similar to [19]. Divide all Δ batches into Δ/d phases, each phase consisting of d consecutive batches. Let D be a parameter which upper bounds the number of batches in which any vertex vR could appear during a single phase. Then, the maximum degree of a single phase would be bounded by Dd, so in principle we should be able to color all edges within this phase using O(Dd) different colors. To implement the coloring procedure, at the beginning of each phase, prepare D fresh palettes C1,C2,,CD, each of size d, and assign each batch in this phase a palette Ci where i is chosen from [D] uniformly at random. To keep track of the colors already used around each vertex, we maintain the following data structures.

  • Each vertex vR keeps a list Uv{C1,C2,,CD} of used palettes.

  • Each vertex uL initializes a random shift ru[d] at the beginning of the algorithm.

When a batch of edges FE arrives, we will use the assigned palette Ci to color this batch. For every edge (u,v)F, if CiUv, then tentatively assign the color (ru+ci)modd in Ci to edge (u,v), where ci denotes the number of times that palette Ci has been assigned to previous batches. If CiUv, we mark the edge as uncolored. Since the palettes are assigned to batches randomly, in expectation, a constant fraction of edges will be successfully colored. In the case that multiple edges incident on v are assigned the same color, we retain only one such edge and mark the remaining edges as uncolored. Since all the random shifts ru’s are uniformly random and independent of the randomness of counters ci, most tentative colors around any vertex vR in this batch should be different. Once the batch F is processed, add Ci to all lists Uv,vR such that degF(v)=d.

To reason about the space usage, we can argue that the total size of the lists Uv,vR does not exceed O(n), because a palette Ci appears in the list Uv only when v receives d edges in a batch which uses palette Ci. Since the total number of edges in a phase is O(dn), the total list size should be bounded by O(n). In this way, we are able to store all the used palettes of vertices in R; this is not new to our approach, and a similar argument was also used in [19]. The new ingredient is the way we store the used colors around vertices in L. Here we have exploited the fact that vertices in L have low degrees in each batch, so their progress in every palette Ci is synchronized; that is, we only need to store a single counter ci which is the number of times that Ci appears, and then the next tentative color of uL would be (ru+ci)modd.

The above scheme would use O(Dd) different colors in a single phase, so O(ΔD) colors across all Δ/d phases. When DΔ1/4, this bound would be much better than Δ1.5. So, what if D>Δ1/4? To deal with this case, we will apply a two-layer approach. Specifically, let us further group every D consecutive phases as a super-phase, so there are at most Δ/Dd<Δ1/4 super-phases in total (recall that we were assuming d>Δ1/2). Within a super-phase, we will allocate Δ fresh colors which are divided into Δ/Dd different color packages P1,P2,,PΔ/Dd, where each color package Pi is further divided into D palettes of size d as Pi=Ci,1Ci,2Ci,D. In this way, the total number of colors would be Δ5/4.

Then, like what we did before, for each phase in a super-phase, assign a color package Pi from P1,P2,,PΔ/Dd uniformly at random. Within each phase, we will stick to its assigned color package Pi and reuse the algorithm within a phase we have described before. Since a color package is shared by multiple phases, each vertex vR needs to store a list Uv,2 which stores all the packages Pi it has used so far, and in any phase where Pi is assigned but Pi is already contained in Uv,2, we would not color any edges incident on v in this particular phase. By repeating the same argument, we can argue that the total size of all the lists Uv,2,vR is bounded by O(n) as well.

We can further generalize this two-layer approach to multiple layers and reduce the total number of colors to Δ1+ϵ. However, this only works with the most unbalanced setting where vertices on L always have constant degrees in each batch of input. In general, when low-degree side has degree d, our algorithm needs dΔ1+ϵ colors. If d is large, then we would switch to the color table approach from [39]. Balancing the two cases, we end up with Δ4/3+ϵ colors overall.

Derandomization using Bipartite Expanders

Randomization is used both in the unbalanced case and in the regular case. To replace the choices of the random shifts ru and random color package assignments, we will show one can apply unbalanced bipartite expanders [42, 34, 35] in a black box manner. However, for the random shifts used in the regular case where we apply the color table idea from [39], it would not be enough to use an arbitrary bipartite expander, because the counters cu’s could be different and possibly damage the expansion guarantee; for example, it is not clear to us how to apply the bipartite expander construction based on Parvaresh–Vardy Codes [34]. To fix this issue, it turns out that it would be most convenient to use the bipartite expander construction based on multiplicity codes [35].

2 Preliminaries

Basic Terminologies

For any integer k, let us conventionally define [k]={1,2,,k}. For any set S and integer k, let kS be the multi-set that contains exactly k copies of each element in S.

Let G=(V,E) denote the simple input graph on n vertices and m edges with maximum degree Δ. For any subset of edges FE and any vertex uV, let degF(u) be the number of edges in F incident on u. Sometimes we will also refer to the subgraph (V,F) simply as F.

Problem Definition

In the edge coloring problem, we need to find an assignment of colors to edges such that adjacent edges have distinct colors, and the objective is to minimize the total number of different colors.

In the W-streaming model introduced by [25, 33], all edges of the graph G arrive one by one in the stream in an arbitrary order, and the algorithm makes one pass over the stream to perform its computation. For the task of edge coloring, since the algorithm has much less space than the total size of the graph, it cannot store all the edge colors in its memory. To output the answer, the algorithm is given a write stream in which it can print all colors.

Next, to set the stage in a convenient way, we will state several reductions for the problem.

General-to-Bipartite Reduction

Let us first simplify the problem by a deterministic reduction from edge coloring in general graphs to bipartite graphs.

Lemma 3 (Corollary 3.2 in [32]).

Given an algorithm 𝒜 for streaming edge coloring on bipartite graphs using f(Δ) colors and g(n,Δ) space, there is an algorithm using O(f(Δ)) colors and O(g(n,Δ)logn+nlognlogΔ) space in general graphs. Furthermore, this reduction is deterministic.

Reduction to Fixed Degree Pairs

By the above reduction, we focus on edge coloring for bipartite graphs G=(V,E), where V=LR. Since the algorithm has space Ω(n), we can divide the input stream into at most O(m/n)=O(Δ) batches, each batch containing n edges. For any vertex uV and any batch F, let degF(u) be the number of edges in F incident on u. For every pair of integers 0l,rlog2Δ and every batch F, let Fl,r={(u,v)FdegF(u)[2l,2l+1),degF(v)[2r,2r+1)}, and define El,r=FFl,r over all batches F in the stream and ml,r=|El,r|.

In the main text, we will devise an algorithm to handle edges in Fl,r for any fixed pair of (l,r). The final coloring is obtained by taking the union of the colors over all (l,r), which will blow up the number of colors and space by a factor of O(log2Δ).

Adapting to an Unknown 𝚫

So far we have assumed that the maximum vertex degree Δ in G is known in advance. Our algorithm can be adapted to an unknown value Δ in a standard way. Specifically, we can maintain the value Δt which is the maximum degree of the subgraph containing the first t edges in the input stream. Whenever Δt(2k1,2k], we apply our algorithm with Δ=2k to color all the edges. When k increments at some point, we restart a new instance of the algorithm with a new choice Δ=2k and continue to color the edges with fresh colors. Overall, the total number of colors will not change asymptotically.

3 Randomized 𝚫𝟒/𝟑+ϵ Edge Coloring

This section is devoted to the proof of Theorem 1.

Reduction to Partial Coloring

To find an edge coloring of a graph, it was shown in [19] that it suffices to color a constant fraction of edges in E if we do not care about O(logΔ) blow-ups in the number of colors. Roughly speaking, for the uncolored edges, we can view them as another instance of edge coloring, and solve it recursively. The following statement formalizes this reduction.

Lemma 4 (implicit in [19]).

Suppose there is a randomized streaming algorithm 𝒜 with space g(n,Δ) space, such that for each edge in eE, it assigns a color from [f(Δ)] or marks it as (uncolored) and print this information in the output stream, with the guarantee that there are at least δm edges in expectation which receive actual colors, for some value δ>0. Then, there is a randomized edge coloring algorithm which uses at most O(logΔδf(Δ)) colors and O(logΔδg(n,Δ)) space in expectation.

Proof sketch.

The idea is to recursively apply the streaming algorithm on all edges marked with (uncolored). In expectation, each time we reapply the algorithm, the number of uncolored edges decrease by a factor of 1δ. So the expected recursion depth would be O(logΔδ) before all uncolored edges fit in memory.

According to the reductions in the preliminaries, we will focus on partial edge coloring in bipartite graphs with fixed degree pairs. More specifically, our algorithm consists of the following two components.

Lemma 5.

Fix a parameter ϵ>0. Given an graph G=(V,E) on n vertices with maximum vertex degree Δ, for any constant ϵ>0, and fix an integer pair (l,r), there is a randomized W-streaming algorithm that outputs a partial coloring of edges Fl,r such that least δml,r edges receive colors in expectation; here δ=2O(1/ϵ) is also a constant. The algorithm uses O((logΔ)O(1/ϵ)Δ1+ϵ2l) colors and O((logΔ)O(1/ϵ)n) space.

Lemma 6.

Given an graph G=(V,E) on n vertices with maximum vertex degree Δ, and fix an integer pair (l,r), there is a randomized W-streaming algorithm that outputs a partial coloring of edges Fl,r such that least ml,r/2 edges receive colors in expectation. The algorithm uses O(Δ+Δ2/2l+r) colors and O(n) space.

Proof of Theorem 1.

Basically, Lemma 5 deals with the case when min{2l,2r} is small, and Lemma 6 deals with the case when min{2l,2r} is large. For any (l,r), if min{2l,2r}Δ1/3, then by Lemma 5, the number of colors is at most O((logΔ)O(1/ϵ)Δ4/3+ϵ), and otherwise by Lemma 6 the number of colors would be O(Δ4/3). Either way, the total number of colors over all (l,r) is bounded by O((logΔ)O(1/ϵ)Δ4/3+ϵ).

3.1 Proof of Lemma 5

3.1.1 Data Structures

Before presenting the details of the data structures we will use in the main algorithm, let us start with a brief technical overview. The data structures consist of three components.

  • Forest structures on batches. This part organizes edge input batches into parameterized forests in a way similar to B-trees. The height of the forests will be O(1/ϵ), and the branch size of each level will be an integer power of 2 in the range [Δϵ,Δ], and so the total number of different forests will be bounded by (logΔ)O(1/ϵ).

  • Color allocation on forests. Each forest will be associated with a separate color set of size roughly Δ1+ϵ. On each level of a forest, we will randomly partition the color set of this forest into color subsets (packages) and assign them to the tree nodes on this level. We will also make sure that the color packages on tree nodes are nested; that is, the color package of a node is a subset of the color package of its parent node.

    Each vertex will choose colors for its incident edges according to its own frequencies of accumulating edges in the stream. For example, when a vertex is gathering a large number of incident edges in a short interval of batches, it would use color packages on tree nodes with large branch sizes.

  • Vertex-wise data structures. To ensure that we never assign the same color to adjacent edges, each vertex needs to remember which colors it has already used around it. To efficiently store all the previously used colors, we will show that the used colors are actually concentrated in color packages, so each vertex only needs to store the tree nodes corresponding to those color packages, instead of storing every used colors individually.

Next, let us turn to the details of the data structures we have outlined above.

Forest Structures on Batches

Without loss of generality, assume lr, 2r>Δϵ, and Δϵ is an integer power of two; note that if 2rΔϵ, then the maximum degree inside each batch Fl,r is at most Δϵ, so we can use a fresh palette of size O(Δϵ), so the total number of colors would be O(Δ1+ϵ).

As we have done in the preliminaries, partition the entire input stream into at most m/nΔ batches of size n. We will create at most (logΔ)O(1/ϵ) different forest structures, where each leaf represents a batch, and the internal tree nodes represent consecutive batches. Each forest is parameterized by an integer vector 𝐟=(f1,f2,,fh) such that:

  • fi is an integer power of two;

  • 2r+1=f0f1f2fh=Δϵ, and 2r+1i=1h1fim/n.

We can assume the total number of batches in the input stream is an integer multiple of 2r+1i=1h1fim/n by padding empty batches. Given such a vector 𝐟=(f1,f2,,fh), we will define a forest structure 𝒯𝐟 with h+1 levels by a bottom-up procedure; basically we will build a forest on all the batches with branching factors 2r+1,f1,,fh bottom-up. More specifically, consider the following inductive procedure.

  • All the batches will be leaf nodes on level 0. Partition the sequence of all batches into groups of consecutive f0=2r+1 batches. For each group, create a tree node at level-1 connecting to all leaf nodes in that group.

  • Given any 1ih1, assume we have defined all the tree nodes on levels 1ji. List all the tree nodes on level i following the same ordering of the batches, and partition this sequence of level-i nodes into groups of size fi. For each group, create a tree node at level-(i+1) that connects to all nodes in the group.

According to the definition, in general, tree levels up to k have the same topological structure for all frequency vectors which share the same first k1 coordinates f1,f2,,fk1. For any node NV(𝒯𝐟), let 𝒯𝐟(N) be the subtree rooted at node N. By the above definition, for any 1kh, for any level-k node N, the set of all leaf nodes contained in the subtree 𝒯𝐟(N) form a sub-interval of the batch sequence with length 2r+1i=1k1fi.

Color Allocation on Forests

Next, we will allocate color packages at each tree node of each forest 𝒯𝐟. By construction, each forest structure 𝒯𝐟 is a tree of h+1 levels (from level-0 to level-h), and each tree is rooted at a level-h node. Go over each tree T𝒯𝐟 and we will allocate color packages to tree nodes in a top-down manner.

  • Basis. At the root N of the tree T, allocate a color package 𝒞N with 252l+r+2i=1h(5fi) new colors. Divide package 𝒞N evenly into 5fh=5Δϵ smaller packages (colors are ordered alphabetically in a package):

    𝒞N=𝒞1N𝒞2N𝒞5ΔϵN

    Here, symbol means disjoint union. By construction of tree T, N has fh1 different children N1,N2,,Nfh1. Let sequence (i1,i2,,i5fh1) be a random permutation of (fh1/Δϵ)[5Δϵ]. For each 1jfh1, define color package 𝒞Nj=𝒞ijN.

  • Induction. In general, suppose we have defined color packages for tree nodes on levels k,k+1,,h. Go over all tree nodes on level k. Inductively, assume |𝒞N|=252l+r+2i=1k(5fi). Divide color package 𝒞N into 5fk smaller packages (colors are ordered alphabetically in a package):

    𝒞N=𝒞1N𝒞2N𝒞5fkN

    Let i1,i2,,i5fk1 be a random permutation of (fk1/fk)[5fk]. For each such level-k node N, by construction, it has fk1 children N1,N2,,Nfk1. Then, for each 1jfk1, define color package 𝒞Nj=𝒞ijN.

By the above construction, each leaf node is allocated a color package of size 252l+r+2. We will call each such smallest color package a palette. Notice that, by definition, the same palette may appear at multiple leaf nodes (which represent input batches). For any leaf node N (or equivalently, a batch), let 𝖼𝗇𝗍(𝒞N) count the total number of times that palette 𝒞N is also allocated to previous leaf nodes (batches). Note that the counters 𝖼𝗇𝗍() do not depend on the input stream and can be computed in advance.

Vertex-Wise Data Structures

To carry out the streaming algorithm, we will also maintain some data structures for vertices in V. At the beginning of the streaming algorithm, for each vertex uL, draw a random shift ru[32r+1] uniformly at random; these random shifts ru’s will remain fixed throughout the entire execution of the algorithm.

The main part is to specify the data structures associated with each vertex vR. For each forest 𝒯𝐟, we will maintain a set of marked nodes Mv,𝐟V(𝒯𝐟) throughout the streaming algorithm.

Invariant 7.

We will ensure the following properties regarding the marked nodes Mv,𝐟 throughout the execution of the streaming algorithm.

  1. (1)

    No two nodes in Mv,𝐟 lie on the same root-to-leaf path in the forest 𝒯𝐟. Furthermore, suppose the current input batch corresponds to a leaf F, and let P be the unique tree path from F to the tree root. Then, any node NMv,𝐟 is a child of some node on P.

  2. (2)

    For any node N𝒯𝐟 on level-k such that Mv,𝐟V(𝒯𝐟(N)) , let F1,F2,,FsE be all the input batches which correspond to leaf nodes in subtree 𝒯𝐟(N). Take the union of the batches U=F1F2Fs. Then, we have degU(v)2rki=1kfi.

  3. (3)

    For any previous input batch F before F such that:

    • F and F are in the same tree component in 𝒯𝐟,

    • degF(v)[2r,2r+1),

    • v used some colors in 𝒞F during the algorithm,

    we guarantee that F must be contained in some subtree 𝒯𝐟(N) for some NMv,𝐟.

  4. (4)

    The choices of Mv,𝐟 is independent of the randomness of {ruuL} and the randomness of color packages 𝒞, and they only depend deterministically on the input stream.

Let us explain the purpose of the above properties. Invariant 7(1)(2) ensures that the algorithm only uses O~(n) space in total. Invariant 7(3) allows us to rule out all colors used previously, preventing duplicate assignments to edges incident on the same vertex. Invariant 7(4) will be technically important for the analysis of randomization.

3.1.2 Algorithm Description

Next, let us turn to describe the coloring procedure. At the beginning, all the marked sets Mv,𝐟 are empty for any vR and any frequency vector 𝐟. Upon the arrival of a new input batch F, we will describe the procedures that update the marked sets and assign edge colors.

Preprocessing Marked Sets

Since the current input batch has changed due to the arrival of F, we may have violated Invariant 7(2) as the root-to-leaf tree path may have changed. Therefore, we first need to update all the marked sets with the following procedure named UpdateMarkSet(F).

Go over every vertex vR and every frequency vector 𝐟. Consider the position of F in the forest 𝒯𝐟, and let P be the root-to-leaf path in 𝒯𝐟 ending at leaf F. First, remove all marked nodes NMv,𝐟 which are not in the same tree as P; note that this may happen when F is the first leaf in a new tree component of 𝒯𝐟.

Next, go over every node W lying on the tree path P, for any child node N of W, if (1) V(𝒯𝐟(N))∌F and (2) V(𝒯𝐟(N))Mv,𝐟, then remove all nodes in V(𝒯𝐟(N))Mv,𝐟 from Mv,𝐟 and add N to Mv,𝐟. In other words, we elevate the positions of all the marked nodes in Mv,𝐟 to their ancestors which are children of P. See Figure 1 for an illustration.

Figure 1: In this picture, it shows an example of a forest 𝒯𝐟 where the orange nodes are the marked ones, and the blue path is the root-to-leaf path ending at the current input batch F. Upon the arrival of a new input batch F, we need to update the root-to-leaf tree path and the marked sets accordingly.
Coloring 𝑭𝒍,𝒓

To find colors for edges in Fl,r, we first need to find a proper palette for each vertex vR such that degF(v)[2r,2r+1). We will describe an algorithm FreqVec(F) which finds a proper frequency vector 𝐟v=(f1,f2,,fh) for each such vR and use the palette 𝒞F associated with leaf node F in the forest 𝒯𝐟v. To identify the proper frequency vector 𝐟v, we will figure out each coordinate f1,f2,,fh one by one inductively.

  • Basis. Let N be the unique level-1 node containing F (recall that level-1 nodes are defined irrespective of frequency vectors). Find f1{Δϵ,2Δϵ,,2r+1} which is the smallest integer such that there exists a frequency vector 𝐟=(f1,f2,f3,), so that Mv,𝐟 contains less than f1 children of N. Note that such a vector must exist, because f1=2r+1 always satisfies this requirement.

    If f1=Δϵ, return the 1-dimensional vector 𝐟v=(f1).

  • Induction. In general, assume we have specified a prefix f1,f2,,fk for some k1. Note that all the forests 𝒯𝐟 share the same topological structures from level 0 up to k+1. Let N be the unique level-(k+1) node containing F conditioning on f1,f2,,fk. Check all the frequency vectors 𝐟 that begin with the prefix f1,f2,,fk, and find the smallest possible fk+1{Δϵ,2Δϵ,,fk} such that there exists a frequency vector 𝐟=(f1,f2,,fk,fk+1,fk+2,) under the condition that Mv,𝐟 contains less than fk+1 children of N. Note that such a vector must exist, because fk+1=fk always satisfies this requirement.

    If fk+1=Δϵ, then return the vector 𝐟v=(f1,f2,,fk,fk+1).

  • Choosing palette 𝒞v. Once we have finished the above inductive process, we need to choose a palette 𝒞v for v which contains 252l+r+2 different colors. Basically, we will choose the palette associated with leaf node F in forest 𝒯𝐟v as 𝒞v, but must ensure that 𝒞v has not been used previously.

    To make sure of this, let P denote the root-to-leaf tree path ending at leaf node F in 𝒯𝐟v. Travel down the path from root to leaf and enumerate all the encountered tree nodes. For every such tree node N, if N already contains a sibling WMv,𝐟v and 𝒞W=𝒞N, then abort this procedure and assign 𝒞v.

    In the end, if this procedure terminates without abortion, then assign 𝒞v𝒞F; here 𝒞F refers to the palette of size 252l+r+2 associated with leaf node F in forest 𝒯𝐟v.

In this way, we can select a frequency vector 𝐟v for every vertex vR such that degF(v)[2r,2r+1). Let 𝒞v be the palette assigned to leaf node F by forest 𝒯𝐟v. Next, we are going to color all edges in Fl,r using colors from 𝒞v for edges incident on vR. Go over each vertex uL, and list its neighbors v1,v2,,vk,k<2l+1 in Fl,r. For any index 1ik, if 𝒞vi, then reserve a tentative color to edge (u,vi), which is the κi-th color in palette 𝒞vi and

κi=52l+1(𝖼𝗇𝗍(𝒞vi)+ru)+imod252l+r+2

Recall that 𝖼𝗇𝗍(𝒞v) counts the number of times that palette 𝒞v has appeared at previous leaf nodes under 𝒯𝐟. Notice that k<2l+1, these tentative colors are different around u.

On the side of vR, it checks all the tentative colors on all of its edges in Fl,r. If a tentative color is used more than once, then it keeps only one of them, and turns other tentative colors back to . Finally, for each edge eFl,r, assign e its own tentative color and print it in the output stream.

Postprocessing Marked Sets

After processing the input batch F, for every vertex vR such that degF(v)[2r,2r+1), add node F to Mv,𝐟v; note that we mark F irrespective of whether 𝒞v is or not as will be important for establishing Invariant 7(4). The whole algorithm is summarized in Algorithm 1.

Algorithm 1 ColorLowDeg(F).

3.1.3 Proof of Correctness

To begin with, let us first bound the total number of different colors that we could possibly use.

Lemma 8.

The total number of colors that the algorithm could use is O((logΔ)O(1/ϵ)Δ1+ϵ2l).

Proof.

By the design of the forest structures, for each frequency vector 𝐟, the number of colors assigned to each tree in the forest 𝒯𝐟 is bounded by 252l+r+2i=1h(5fi). Since each tree in 𝒯𝐟 covers 2r+1i=1h1fi batches, and there are at most m/nΔ batches, the total number of colors in 𝒯𝐟 is bounded by

252l+r+2i=1h(5fi)Δ2r+1i=1h1fi=O(Δ1+ϵ2l5O(1/ϵ)).

Since there are (logΔ)O(1/ϵ) different choices for 𝐟, the total number of colors used by the algorithm is O((logΔ)O(1/ϵ)Δ1+ϵ2l).

Let us next state some basic properties of any forest 𝒯𝐟.

Lemma 9.

Each palette is used by at most 2r+1/Δϵ different batches.

Proof.

Consider a palette 𝒞N allocated to a leaf node N. By the construction of color packages:

  • At the root, exactly one package contains this palette, and fh1/Δϵ children of the root inherit the palette. Therefore, at level h1, the palette 𝒞N is used in at most fh1/Δϵ nodes.

  • Suppose at level k, the palette 𝒞N is used in fk/Δϵ nodes. Each of these nodes has fk1/fk children that inherit the palette. Thus, at level k1, the palette is used in at most fk1/Δϵ nodes.

By induction, the palette 𝒞N is used in at most 2r+1/Δϵ different batches at level 0, as required.

Corollary 10.

During the algorithm, the values of the counters 𝖼𝗇𝗍(𝒞) never exceed 2r+1/Δϵ for any palette 𝒞.

To bound the total space, it is clear that the bottleneck is storing all the marked sets Mv,𝐟, since all the forest structures and color assignments only require space O((logΔ)O(1/ϵ)Δ).

Lemma 11.

If Invariant 7 is satisfied, then at any point during the execution of the algorithm, for any given frequency vector 𝐟, the total size of marked sets vR|Mv,𝐟| is bounded by O(2hn). Consequently, the total space usage is bounded by O((logΔ)O(1/ϵ)n).

Proof.

For any level-k vertex N𝒯𝐟, the subtree 𝒯𝐟(N) contains exactly 2r+1i=1k1fi batches, and thus 2r+1i=1k1fin edges. Let U denote the union of all batches in 𝒯𝐟(N). For any vertex v, if Mv,𝐟N, by Invariant 7(2), we have degU(v)2rki=1kfi. Thus, the number of vertices v such that Mv,𝐟N is bounded by:

2r+1i=1k1fin2rki=1kfi=2k+1nfk.

Suppose the current working batch is F. By Invariant 7(1), any marked vertex is a child of a node on the root-to-leaf path P. Thus, among all vertices at level k, there are fk vertices that are candidates for being marked. Taking the summation over all levels, the total size of vR|Mv,𝐟| is bounded by

vR|Mv,𝐟|k=0h+12k+1nfkfk=O(2hn).

Since the depth of the tree is at most O(1/ϵ), and there are O((logΔ)O(1/ϵ)) distinct frequency vectors 𝐟, the total space usage is therefore bounded by O((logΔ)O(1/ϵ)n).   Now, our main focus will be on verifying all the properties in Invariant 7.

Lemma 12.

Invariant 7 is preserved by the algorithm throughout its execution.

Proof.

Property (1) is preserved in a straightforward manner by the way we maintain all the marked sets Mv,𝐟 in the pre- and post-processing step for each input batch. Property (4) is also guaranteed because our updates to marked sets only depend on the input stream, not on the randomness used by the algorithm.

As for property (3), according to the coloring algorithm, for any previous input batch F where degF(v)[2r,2r+1), if vertex vR used some colors associated with leaf node F in forest 𝒯𝐟, then the algorithm must have added F to Mv,𝐟 back then. Then, according to the preprocessing rules, F would always be contained in the subtree of some marked as long as the current leaf node F belongs to the same connected tree component as F in 𝒯𝐟.

Next, we will focus on property (2). We will prove this by an induction on time. As the basis, property (2) holds trivially because all the marked sets are empty. Consider the arrival of any new input batch F and any vertex vR such that degF(v)[2r,2r+1).

First, we argue that the pre-processing step does not harm property (2). This is because the inequality in property (2) is required for all ancestors of any marked node (including itself), so if it held right before the arrival of F, then it should also hold after the pre-processing step as we are only raising the positions of marked nodes to their ancestors.

Next, we consider the coloring step and the post-processing step. According to the coloring procedure, since v will only use colors and mark nodes in forest 𝒯𝐟v, we will only need to worry about property (2) in forest 𝒯𝐟v. Before the post-processing step, let P be the root-to-leaf path ending at leaf node F in 𝒯𝐟v, and let W be the highest (in terms of levels) node on P such that V(𝒯𝐟v(W))Mv,𝐟v=, namely the subtree 𝒯𝐟v(W) does not contain any marked nodes; this node W always exists because F itself is a possible candidate.

To prove property (2) after we add F to Mv,𝐟v, we only need to verify the inequality for all nodes on P between W and F. List all these nodes as F=N0,N1,N2,,Nk=W. We will prove the inequality of property (2) for each index i=0,1,,k.

  • When i=0, we already know that degF(v)2r, so the inequality holds.

  • For any index 1ik, consider the procedure that chose the coordinate fi. Because of the minimality of fi, we know that for some alternate frequency vector 𝐟=(f1,f2,,fi1,fi/2,), there are at least fi/2 marked children of Ni (before the post-processing step), where NiV(𝒯𝐟) sits at the same topological position as Ni (or in other words, 𝒯𝐟v(Ni) and 𝒯𝐟(Ni) are isomorphic). Let U be the union of the batches which are all leaf nodes of 𝒯𝐟(Ni). Therefore, by our inductive assumption regarding property (2), we know that:

    degU(v)(fi/2)2ri+1j=1i1fj=2rij=1ifj

    This verifies the inequality at node Ni.

Next, let us turn to the color assignment part. First, we need to verify that the algorithm never assigns the same color twice around the neighborhood of a single vertex.

Lemma 13.

In the output stream, the algorithm never prints the same color for two adjacent edges.

Proof.

First, let us rule out color conflicts for edges around the same vertex uL. This is rather straightforward, because according to the algorithm description, within each batch, we only assign tentative colors with distinct color indices around each vertex uL. For two different batches F,F, if we happen to use the same color palette 𝒞 in F,F around the same vertex u, then the counter values 𝖼𝗇𝗍(𝒞) must be different in these two batches. According to Corollary 10 and that ru[32r+1], the value of 𝖼𝗇𝗍(𝒞v+ru) is always in the range [32r+1,42r+1]. Together with the fact that degF(u),degF(u)<2l+1, the algorithm must use distinct colors in F,F from 𝒞.

Next, let us rule out color conflicts for edges around the same vertex vR. For any color palette provided by 𝒯𝐟v which was used before in some previous batch F, according to Invariant 7(3), there must be a marked node N whose subtree contains F. According to our coloring procedure, 𝒞v is nonempty only when 𝒞N is disjoint from all the color packages of its marked siblings N, for any node N on the root-to-leaf path to F in 𝒯𝐟v. Therefore, v could not reuse any palettes previously assigned. Furthermore, since we discard repeated colors within a single palette, the assigned colors must be distinct.

Finally, let us prove that the algorithm successfully colors a good fraction of all edges in the input stream.

Lemma 14.

The total number of colored edges in the output stream is at least δm in expectation, where δ=2O(1/ϵ).

Proof.

Fix any input batch F and any vertex vR such that degF(v)[2r,2r+1), it suffices to lower bound the expected number of colored edges in Fl,r incident on v.

First, we need to analyze the probability that the color palette 𝒞v is nonempty, based on the randomness of the distribution of color packages on forest 𝒯𝐟v. As before, let P denote the root-to-leaf path in 𝒯𝐟v ending at F, and let F=N0,N1,,Nh be all the nodes on the tree path. According to the selection of the frequency vector 𝐟v, for any 0kh1, Nk has less than fk+1 marked siblings. By design, the color packages of Nk+1 are determined by the length-fk prefix of a random permutation (fk/fk+1)[5fk+1]. Therefore, by the independence guarantee from Invariant 7(4), the probability that 𝒞Nk does not conflict with the color packages of any other marked siblings is at least (11/(5fk+1))fk+14/5. By applying this bound over all levels, the probability that 𝒞v is nonempty is at least (4/5)h(4/5)1/ϵ.

Next, conditioning on the event that 𝒞v, let us analyze the amount of edges in Fl,r that are colored around v. Let u1,u2,,uk be the neighbors of v in graph (V,Fl,r), where k<2r+1. For any fixed 1ik, as rui was chosen uniformly at random from [32r+1], the probability that ruiruj for all ji is at least (11/(32r+1))k2/3. This ensures that the tentative colors between ui and v survive in the output stream with probability at least 2/3.

Overall, the expected number of colored edges in Fl,r would be at least (2/3)(4/5)1/ϵ|Fl,r|, which concludes the proof.

3.2 Proof of Lemma 6

Without loss of generality, assume Δ is a power of 2.

3.2.1 Data Structures

At the beginning, for each vertex uL, draw a random number su[Δ/2l] uniformly at random. For each vertex vR, draw a random number tv[Δ/2r] uniformly at random.

As in the preliminary steps, the input stream is divided into batches of size n (except for the last one). For each uL, let 𝖼𝗇𝗍(u) count the number of previous batches F where degF(u)[2l,2l+1), and symmetrically let 𝖼𝗇𝗍(v) count the number of previous batches F where degF(v)[2r,2r+1) for vR.

Additionally, we will use a palette matrix 𝒞 of size Δ2l×Δ2r, where each entry in 𝒞[i,j] corresponds to a distinct palette of size Δ0, with Δ04(2l+r+1Δ+1). All the colors can be represented as integers in the range [Δ0Δ22l+r] naturally.

3.2.2 Algorithm Description

Let us describe the coloring procedure upon the arrival of a new input batch F. For each vertex uL, propose a tentative row index xu=(su+𝖼𝗇𝗍(u))modΔ2l. For each vertex vR, propose a tentative column index yv=(tv+𝖼𝗇𝗍(v))modΔ2r. For each edge (u,v)F, we will assign a color from the matrix 𝒞[xu,yv] in the following manner.

Let Ex,y be the set of edges (u,v)Fl,r where (xu,yv)=(x,y), and let Gx,y be the subgraph whose edge set is Ex,y. To color Gx,y with only Δ0 colors, we need to prune it so that its maximum degree does not exceed Δ0, which is done in this way: for each edge (u,v)Ex,y, if max{degEx,y(u),degEx,y(v)}>Δ0, mark it as (uncolored) and remove it from Gx,y. Finally, since Gx,y is a bipartite graph, we can apply the Δ0-edge coloring algorithm [23] to color Gx,y using the palette 𝒞[x,y] which has size Δ0.

Finally, for each vertex uL such that degF(u)[2l,2l+1), increment the counter 𝖼𝗇𝗍(u) by 1; also, increment the counters for vR in a symmetric way. The whole algorithm is summarized in Algorithm 2.

Algorithm 2 ColorHighDeg(F).

3.2.3 Proof of Correctness

Proper Coloring

To prove that the colored edges form a proper coloring, we need to show that for any two distinct edges e1=(u,v1) and e2=(u,v2) sharing a common vertex u, their colors are different. Since the algorithm is symmetric for L and R, we can assume uL. There are several cases below.

  • If e1 and e2 use different matrix entries in 𝒞, their colors are already distinct.

  • Suppose both edges use palette 𝒞[x,y]. Then, there are two sub-cases below.

    • If e1 and e2 belong to different batches F1 and F2 with batch counters 𝖼𝗇𝗍(1)(u) and 𝖼𝗇𝗍(2)(u), we have xsu+𝖼𝗇𝗍(1)(u)su+𝖼𝗇𝗍(2)(u)(modΔ/2l). Since degF(u)[2l,2l+1), 𝖼𝗇𝗍u never exceeds Δ/2l. Thus, 𝖼𝗇𝗍(1)(u)=𝖼𝗇𝗍(2)(u), which leads to a contradiction.

    • If e1 and e2 belong to the same batch, they belong to the same subgraph Gx,y. The correctness of the offline coloring algorithm guarantees they get distinct colors.

Space Usage

For each vertex u, we maintain its batch counter 𝖼𝗇𝗍u and random shift su for uL (or tv for vR), requiring O(n) space in total. During the batch coloring process, we also store the indices xu and yv, which require additional O(n) space. Furthermore, each subgraph Gx,y has at most n edges, so the offline coloring algorithm requires O(n) space. These spaces are reused across different subgraph coloring processes and different batches. Therefore, the overall space complexity is O(n).

Number of Colors

The total number of colors is given by

Δ2lΔ2rΔ0=O(Δ+Δ22l+r).

Next, we show that at least half of the edges get colored in expectation.

Lemma 15.

During the algorithm, at least a 1/2 fraction of the edges are colored in expectation.

Proof.

For any edge (u,v)Fl,r such that uL,vR, we estimate the probability that (u,v) is colored. Define x=xu,y=yv. It suffices to lower bound the probability that degEx,y(u),degEx,y(v)Δ0.

Let (u,v1),(u,v2),,(u,vk)Fl,r,k<2l+11 be all edges incident on u other than (u,v). Since G is a simple graph, all the vertices v1,v2,,vk are distinct and are different from v. Since yvi is uniformly distributed in [Δ/2r], the probability that yvi=y is at most 2r/Δ. Using Markov’s inequality, we have:

Pr[degEx,y(u)Δ0](2l+12)2r/ΔΔ01/4

Symmetrically, we can argue that Pr[degEx,y(v)Δ0]1/4. Hence, the probability that (u,v) remains in Ex,y after the pruning procedure would be at least 1/2. This concludes the proof.

References

  • [1] Mohammad Ansari, Mohammad Saneian, and Hamid Zarrabi-Zadeh. Simple streaming algorithms for edge coloring. In 30th Annual European Symposium on Algorithms (ESA 2022). Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2022.
  • [2] Eshrat Arjomandi. An efficient algorithm for colouring the edges of a graph with Δ+1 colours. INFOR: Information Systems and Operational Research, 20(2):82–101, 1982.
  • [3] Sepehr Assadi. Faster Vizing and Near-Vizing Edge Coloring Algorithms. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025.
  • [4] Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, and Tianyi Zhang. Vizing’s theorem in near-linear time. arXiv preprint arXiv:2410.05240, 2024. doi:10.48550/arXiv.2410.05240.
  • [5] Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Distributed edge coloring in time polylogarithmic in Δ. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, pages 15–25, 2022. doi:10.1145/3519270.3538440.
  • [6] Leonid Barenboim and Tzalik Maimon. Fully-dynamic graph algorithms with sublinear time inspired by distributed computing. In International Conference on Computational Science (ICCS), volume 108 of Procedia Computer Science, pages 89–98. Elsevier, 2017. doi:10.1016/J.PROCS.2017.05.098.
  • [7] Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, and Hamed Saleh. Streaming and massively parallel algorithms for edge coloring. In 27th Annual European Symposium on Algorithms (ESA 2019). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019.
  • [8] Anton Bernshteyn. A fast distributed algorithm for (Δ+1)-edge-coloring. J. Comb. Theory, Ser. B, 152:319–352, 2022.
  • [9] Sayan Bhattacharya, Din Carmon, Martín Costa, Shay Solomon, and Tianyi Zhang. Faster (Δ+1)-Edge Coloring: Breaking the mn Time Barrier. In 65th IEEE Symposium on Foundations of Computer Science (FOCS), 2024.
  • [10] Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai. Dynamic Algorithms for Graph Coloring. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1–20. SIAM, 2018. doi:10.1137/1.9781611975031.1.
  • [11] Sayan Bhattacharya, Martín Costa, Nadav Panski, and Shay Solomon. Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2024. doi:10.1137/1.9781611977912.122.
  • [12] Sayan Bhattacharya, Martín Costa, Shay Solomon, and Tianyi Zhang. Even Faster (Δ+1)-Edge Coloring via Shorter Multi-Step Vizing Chains. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025. (to appear).
  • [13] Sayan Bhattacharya, Fabrizio Grandoni, and David Wajc. Online edge coloring algorithms via the nibble method. In Proceedings of theACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2830–2842. SIAM, 2021. doi:10.1137/1.9781611976465.168.
  • [14] Joakim Blikstad, Ola Svensson, Radu Vintan, and David Wajc. Online edge coloring is (nearly) as easy as offline. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC). ACM, 2024. doi:10.1145/3618260.3649741.
  • [15] Joakim Blikstad, Ola Svensson, Radu Vintan, and David Wajc. Deterministic Online Bipartite Edge Coloring. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025.
  • [16] Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto. Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma. ACM Trans. Algorithms, 16(1):8:1–8:51, 2020. doi:10.1145/3365004.
  • [17] Moses Charikar and Paul Liu. Improved algorithms for edge colouring in the w-streaming model. In Symposium on Simplicity in Algorithms (SOSA), pages 181–183. SIAM, 2021. doi:10.1137/1.9781611976496.20.
  • [18] Shiri Chechik, Hongyi Chen, and Tianyi Zhang. Improved streaming edge coloring, 2025. arXiv:2504.16470.
  • [19] Shiri Chechik, Doron Mukhtar, and Tianyi Zhang. Streaming Edge Coloring with Subquadratic Palette Size. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1–40:12, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2024.40.
  • [20] Aleksander B. G. Christiansen. Deterministic dynamic edge-colouring. CoRR, abs/2402.13139, 2024. doi:10.48550/arXiv.2402.13139.
  • [21] Aleksander Bjørn Grodt Christiansen. The Power of Multi-step Vizing Chains. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), pages 1013–1026. ACM, 2023. doi:10.1145/3564246.3585105.
  • [22] Ilan Reuven Cohen, Binghui Peng, and David Wajc. Tight bounds for online edge coloring. In 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 1–25. IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.00010.
  • [23] Richard Cole, Kirstin Ost, and Stefan Schirra. Edge-coloring bipartite multigraphs in o (e logd) time. Combinatorica, 21(1):5–12, 2001. doi:10.1007/S004930170002.
  • [24] Peter Davies. Improved distributed algorithms for the lovász local lemma and edge coloring. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4273–4295. SIAM, 2023. doi:10.1137/1.9781611977554.CH163.
  • [25] Camil Demetrescu, Irene Finocchi, and Andrea Ribichini. Trading off space for passes in graph streaming problems. ACM Transactions on Algorithms (TALG), 6(1):1–17, 2009. doi:10.1145/1644015.1644021.
  • [26] Ran Duan, Haoqing He, and Tianyi Zhang. Dynamic edge coloring with improved approximation. In 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019.
  • [27] Aditi Dudeja, Rashmika Goswami, and Michael Saks. Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025.
  • [28] Michael Elkin, Seth Pettie, and Hsin-Hao Su. (2Δ1)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 355–370. SIAM, 2014.
  • [29] Manuela Fischer, Mohsen Ghaffari, and Fabian Kuhn. Deterministic distributed edge-coloring via hypergraph maximal matching. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 180–191. IEEE, 2017. doi:10.1109/FOCS.2017.25.
  • [30] Harold N Gabow, Takao Nishizeki, Oded Kariv, Daneil Leven, and Osamu Terada. Algorithms for edge coloring. Technical Rport, 1985.
  • [31] Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, and Jara Uitto. Deterministic distributed edge-coloring with fewer colors. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 418–430, 2018. doi:10.1145/3188745.3188906.
  • [32] Prantar Ghosh and Manuel Stoeckl. Low-memory algorithms for online edge coloring. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024.
  • [33] Christian Glazik, Jan Schiemann, and Anand Srivastav. Finding euler tours in one pass in the w-streaming model with o (n log (n)) ram. arXiv preprint arXiv:1710.04091, 2017. arXiv:1710.04091.
  • [34] Venkatesan Guruswami, Christopher Umans, and Salil Vadhan. Unbalanced expanders and randomness extractors from parvaresh–vardy codes. Journal of the ACM (JACM), 56(4):1–34, 2009. doi:10.1145/1538902.1538904.
  • [35] Itay Kalev and Amnon Ta-Shma. Unbalanced expanders from multiplicity codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.
  • [36] Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney, and Jakub Tarnawski. Online edge coloring via tree recurrences and correlation decay. In 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 104–116. ACM, 2022. doi:10.1145/3519935.3519986.
  • [37] Alessandro Panconesi and Romeo Rizzi. Some simple distributed algorithms for sparse networks. Distributed computing, 14(2):97–100, 2001. doi:10.1007/PL00008932.
  • [38] Amin Saberi and David Wajc. The greedy algorithm is not optimal for on-line edge coloring. In 48th International Colloquium on Automata, Languages, and Programming (ICALP), volume 198 of LIPIcs, pages 109:1–109:18, 2021. doi:10.4230/LIPICS.ICALP.2021.109.
  • [39] Mohammad Saneian and Soheil Behnezhad. Streaming edge coloring with asymptotically optimal colors. In 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, volume 297 of LIPIcs, pages 121:1–121:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.ICALP.2024.121.
  • [40] Claude E Shannon. A theorem on coloring the lines of a network. Journal of Mathematics and Physics, 28(1-4):148–152, 1949.
  • [41] Corwin Sinnamon. Fast and simple edge-coloring algorithms. arXiv preprint arXiv:1907.03201, 2019.
  • [42] Amnon Ta-Shma, Christopher Umans, and David Zuckerman. Loss-less condensers, unbalanced expanders, and extractors. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 143–152, 2001. doi:10.1145/380752.380790.
  • [43] Vadim G Vizing. The chromatic class of a multigraph. Cybernetics, 1(3):32–41, 1965.