arxiv: 2605.07774 · v1 · submitted 2026-05-08 · 💻 cs.DS

Recognition: no theorem link

Beyond Brooks: (Delta-1)-Coloring in Semi-Streaming

Maxime Flin , Magn\'us M. Halld\'orsson

Authors on Pith no claims yet

Pith reviewed 2026-05-11 02:20 UTC · model grok-4.3

classification 💻 cs.DS

keywords graph coloringsemi-streamingone-pass algorithmsReed's theoremBrooks' theoremspace lower boundsmaximum degreeedge streams

0 comments

The pith

A one-pass semi-streaming algorithm computes a (Δ-1)-coloring for graphs with maximum degree at least 10^14 and no Δ-clique.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that Reed's existential result on (Δ-1)-colorability can be turned into an explicit algorithm that works in the semi-streaming model with only one pass over the input edges. This matters because many large graphs arrive as edge streams, and classical coloring algorithms usually require multiple passes or more space. The authors also give a matching-style space lower bound showing that any one-pass algorithm attempting to use Δ-k colors, for small k, must use linear space in n scaled by k. Together these results place Reed-type coloring inside the resource limits of streaming computation while proving that further color reductions cost more space.

Core claim

We design a one-pass semi-streaming algorithm for computing a (Δ-1)-coloring of graphs with maximum degree Δ ≥ 10^14 that contain no clique of size Δ. Additionally, we prove that any one-pass (Δ-k)-coloring algorithm for 0 ≤ k < (Δ+1)/2 requires Ω(n(k+1)) space.

What carries the argument

A one-pass algorithm that processes an arbitrary edge stream and maintains a limited-size data structure sufficient to assign each vertex a color from 1 to Δ-1 with no monochromatic edges.

If this is right

Graphs satisfying Reed's conditions admit (Δ-1)-colorings computable with one pass and semi-streaming space.
For any fixed k < (Δ+1)/2, (Δ-k)-coloring in one pass requires Ω(n(k+1)) space.
The space lower bound is linear in the number of vertices even when only one color is saved.
Classical non-streaming coloring results can be lifted to the semi-streaming setting when the degree is sufficiently large.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Reed's theorem becomes algorithmic rather than purely existential once the graph is presented as a stream.
The lower bound suggests that attempts to color with substantially fewer than Δ colors will be space-expensive in the one-pass model.
Similar streaming techniques might apply to other coloring results that hold only for large Δ.
In practice this could allow color-based scheduling or resource allocation on massive graphs that fit the degree and clique conditions.

Load-bearing premise

The input graph has maximum degree at least 10^14 and contains no clique of size equal to its maximum degree.

What would settle it

A graph with maximum degree ≥ 10^14, no Δ-clique, on which the algorithm either uses a color larger than Δ-1 or produces two adjacent vertices with the same color.

Figures

Figures reproduced from arXiv: 2605.07774 by Magn\'us M. Halld\'orsson, Maxime Flin.

**Figure 1.** Figure 1: The three types of subgraphs G[X] such that any coloring of G[V − X] can be extended to a coloring of G. The vertices inside the gray circle are in the almostclique. Figure 1a represent an almost-clique with an induced 2-anti-matching. Figure 1b represents an almost-clique with a 3-independent set. Figure 1c represents a (∆ − 1)- clique with two vertices sharing a neighbor in the clique, each with a diffe… view at source ↗

**Figure 2.** Figure 2: A (∆ − 1)-clique in different configurations. On Figure 2a it has many different external neighbors. On Figure 2b, all vertices are either adjacent to s1 on the left or s2 on the right. If slack generation colors s1 and s2 the same, there is no way to extend the coloring. On Figure 2c, a representation of the Reed Transform: the clique is removed, and the dashed edge added to the graph; the coloring can be… view at source ↗

**Figure 3.** Figure 3: One gadget from the lower bound with ∆ = 7 and c = 6. In black are the edges of C, known to both players, and in gray the pairs used to encode the bits of x. The edges known/added by Alice are represented in red, and the edges known/added by Bob are represented in blue. Here x = 10101011011000 as read on the right with the edges between A and B, and i = 1 since the edges of Bob are incident to the first gr… view at source ↗

read the original abstract

Reed [J.~Comb.~Theory B, 1999] showed that graphs of maximum degree $\Delta \geq 10^{14}$ without $\Delta$-cliques are $(\Delta-1)$-colorable. We design a one-pass semi-streaming algorithm for computing such a coloring. Additionally, we prove that any one-pass $(\Delta-k)$-coloring algorithm for $0\leq k < (\Delta+1)/2$ requires $\Omega(n(k+1))$ space.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives the first one-pass semi-streaming algorithm realizing Reed's (Δ-1)-coloring for huge-degree graphs without Δ-cliques, plus a tight space lower bound for fewer colors.

read the letter

The paper gives the first one-pass semi-streaming algorithm that computes a (Δ-1)-coloring for graphs with maximum degree at least 10^14 and no Δ-clique. It also proves a space lower bound of Ω(n(k+1)) for any one-pass algorithm trying to (Δ-k)-color when k is smaller than (Δ+1)/2. This is new because previous streaming work on coloring had not reached the (Δ-1) bound from Reed's theorem. The algorithm translates the combinatorial guarantee into a streaming procedure, likely by keeping track of neighborhoods or using some greedy coloring with extra space for the special case. The lower bound comes from a communication complexity reduction, which is the standard way to prove streaming space bounds. The paper does well by staying close to the existing theorem and not overclaiming. It focuses on the one-pass model and semi-streaming space. The proofs seem to follow directly without circularity or fitted parameters. A soft spot is the enormous size of Δ required. For any realistic graph this result does not apply, though that is Reed's limitation rather than the paper's. Another minor point is that the algorithm must work under the promise that there is no Δ-clique; in a true streaming setting without promises, you might need to handle cases where the coloring does not exist, but the paper sticks to the promised case. This paper is for researchers in theoretical computer science who look at streaming and graph algorithms. Someone interested in how classical graph theory results can be made algorithmic in restricted models will get something from it. The lower bound also helps understand the limits. It deserves a serious referee because the algorithmic contribution is concrete and the lower bound is tight in the stated range. I recommend sending it for peer review.

Referee Report

0 major / 2 minor

Summary. The manuscript presents a one-pass semi-streaming algorithm that computes a (Δ-1)-coloring for graphs with maximum degree Δ ≥ 10^14 containing no K_Δ, directly realizing Reed's 1999 theorem. It also establishes an Ω(n(k+1)) space lower bound for any one-pass algorithm computing a (Δ-k)-coloring when 0 ≤ k < (Δ+1)/2.

Significance. If the claims hold, the work is significant because it supplies the first explicit one-pass semi-streaming construction realizing Reed's existential (Δ-1)-colorability result for the stated regime, together with a standard information-theoretic lower bound obtained via reduction from multi-party communication. This extends streaming graph algorithms beyond Brooks' theorem while demonstrating near-tightness of the space bound for a range of k.

minor comments (2)

[Abstract] The abstract and introduction should explicitly state the space complexity achieved by the algorithm (e.g., O(n polylog n)) to make the semi-streaming claim precise and comparable to the lower bound.
[Section 3] Section 3 (algorithm description) would benefit from a high-level pseudocode or diagram illustrating how the one-pass procedure invokes the coloring guaranteed by Reed's theorem without requiring multiple passes.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our manuscript and for recommending minor revision. The referee's summary accurately captures both the algorithmic result realizing Reed's theorem in the semi-streaming model and the accompanying space lower bound. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's central claims rest on Reed's 1999 external theorem (cited as an independent combinatorial result guaranteeing (Δ-1)-colorability for the stated regime) together with a direct one-pass semi-streaming construction and a standard information-theoretic lower bound obtained via reduction from multi-party communication. No self-citations are load-bearing for the existence or algorithmic steps, no fitted parameters are renamed as predictions, and no derivation reduces by construction to its own inputs or prior author work. The algorithm and lower bound are independently verifiable against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central algorithmic claim rests on Reed's 1999 theorem as an external existence result; no free parameters are fitted and no new entities are postulated.

axioms (1)

domain assumption Reed's theorem: every graph with maximum degree Δ ≥ 10^14 and no K_Δ is (Δ-1)-colorable.
Invoked in the abstract and used as the existence guarantee that the streaming algorithm must compute.

pith-pipeline@v0.9.0 · 5373 in / 1215 out tokens · 29910 ms · 2026-05-11T02:20:36.011357+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

52 extracted references · 52 canonical work pages

[1]

Palette Sparsification Beyond (

Noga Alon and Sepehr Assadi , editor =. Palette Sparsification Beyond (. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques,. 2020 , url =

work page 2020
[2]

Sublinear Algorithms for (

Sepehr Assadi and Yu Chen and Sanjeev Khanna , editor =. Sublinear Algorithms for (. Proceedings of the Thirtieth Annual. 2019 , url =

work page 2019
[3]

TheoretiCS , volume =

Sepehr Assadi and Pankaj Kumar and Parth Mittal , title =. TheoretiCS , volume =. 2023 , url =

work page 2023
[4]

Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions , booktitle =

Sepehr Assadi and Chen Wang , editor =. Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions , booktitle =. 2022 , url =

work page 2022
[5]

Journal of Combinatorial Theory, Series B , volume =

On an upper bound of a graph's chromatic number, depending on the graph's degree and density , author =. Journal of Combinatorial Theory, Series B , volume =. 1977 , url =

work page 1977
[6]

Leonid Barenboim and Michael Elkin and Seth Pettie and Johannes Schneider , title =. J. 2016 , url =

work page 2016
[7]

2021 , url =

Artur Czumaj and Peter Davies and Merav Parter , title =. 2021 , url =

work page 2021
[8]

The Complexity of (

Yi. The Complexity of (. Proceedings of the 2019. 2019 , url =

work page 2019
[9]

Distributed (

Yi. Distributed (. 2020 , url =

work page 2020
[10]

Probabilistic Tools for the Analysis of Randomized Optimization Heuristics , booktitle =

Benjamin Doerr , editor =. Probabilistic Tools for the Analysis of Randomized Optimization Heuristics , booktitle =. 2020 , url =

work page 2020
[11]

Michael Elkin and Seth Pettie and Hsin. (2. Proceedings of the Twenty-Sixth Annual. 2015 , url =

work page 2015
[12]

A Distributed Palette Sparsification Theorem , booktitle =

Maxime Flin and Mohsen Ghaffari and Magn. A Distributed Palette Sparsification Theorem , booktitle =. 2024 , url =

work page 2024
[13]

Faster Dynamic (

Maxime Flin and Magn. Faster Dynamic (. 52nd International Colloquium on Automata, Languages, and Programming,. 2025 , url =

work page 2025
[14]

Distributed Comput

Maxime Flin and Parth Mittal , title =. Distributed Comput. , volume =. 2025 , url =

work page 2025
[15]

Saks and Srikanth Srinivasan , title =

Dmitry Gavinsky and Shachar Lovett and Michael E. Saks and Srikanth Srinivasan , title =. Random Struct. Algorithms , volume =. 2015 , url =

work page 2015
[16]

Efficient randomized distributed coloring in

Magn. Efficient randomized distributed coloring in. 2021 , url =

work page 2021
[17]

Near-optimal distributed degree+1 coloring , booktitle =

Magn. Near-optimal distributed degree+1 coloring , booktitle =. 2022 , url =

work page 2022
[18]

Ultrafast Distributed Coloring of High Degree Graphs , year =

Magn. Ultrafast Distributed Coloring of High Degree Graphs , year =. doi:10.48550/arXiv.2105.04700 , url =. 2105.04700 , eprintclass =

work page doi:10.48550/arxiv.2105.04700
[19]

2020 , url =

Distributed Algorithms , author =. 2020 , url =

work page 2020
[20]

Harris and Johannes Schneider and Hsin

David G. Harris and Johannes Schneider and Hsin. Distributed (. J. 2018 , url =

work page 2018
[21]

1992 , url =

Nathan Linial , title =. 1992 , url =

work page 1992
[22]

Three Short Proofs in Graph Theory , journal =

L. Three Short Proofs in Graph Theory , journal =. 1975 , issn =

work page 1975
[23]

Reed , title =

Michael Molloy and Bruce A. Reed , title =. J. Comb. Theory. 2014 , url =

work page 2014
[24]

Reed , title =

Bruce A. Reed , title =. J. Graph Theory , volume =

work page
[25]

Journal of Combinatorial Theory, Series B , volume =

A strengthening of Brooks' theorem , author =. Journal of Combinatorial Theory, Series B , volume =. 1999 , url =

work page 1999
[26]

2002 , publisher =

Graph colouring and the probabilistic method , author =. 2002 , publisher =

work page 2002
[27]

Communication Complexity: and Applications

Rao, Anup and Yehudayoff, Amir , publisher =. Communication Complexity: and Applications , year =. doi:10.1017/9781108671644 , location =

work page doi:10.1017/9781108671644
[28]

Fast Distributed Brooks' Theorem , booktitle =

Manuela Fischer and Magn. Fast Distributed Brooks' Theorem , booktitle =. 2023 , url =

work page 2023
[29]

Mathematical Proceedings of the Cambridge Philosophical Society , volume =

On colouring the nodes of a network , author =. Mathematical Proceedings of the Cambridge Philosophical Society , volume =. 1941 , url =

work page 1941
[30]

Adversarially Robust Coloring for Graph Streams , booktitle =

Amit Chakrabarti and Prantar Ghosh and Manuel Stoeckl , editor =. Adversarially Robust Coloring for Graph Streams , booktitle =. 2022 , url =

work page 2022
[31]

Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming! , booktitle =

Anup Bhattacharya and Arijit Bishnu and Gopinath Mishra and Anannya Upasana , editor =. Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming! , booktitle =. 2021 , url =

work page 2021
[32]

Deterministic graph coloring in the streaming model , booktitle =

Sepehr Assadi and Andrew Chen and Glenn Sun , editor =. Deterministic graph coloring in the streaming model , booktitle =. 2022 , url =

work page 2022
[33]

Simple Sublinear Algorithms for (

Sepehr Assadi and Helia Yazdanyar , editor =. Simple Sublinear Algorithms for (. 2025 Symposium on Simplicity in Algorithms,. 2025 , url =

work page 2025
[34]

L. S. Melnikov and V. G. Vizing , title =. Journal of Combinatorial Theory , volume =. 1969 , issn =

work page 1969
[35]

Dynamic Algorithms for Graph Coloring , booktitle =

Sayan Bhattacharya and Deeparnab Chakrabarty and Monika Henzinger and Danupon Nanongkai , editor =. Dynamic Algorithms for Graph Coloring , booktitle =. 2018 , url =

work page 2018
[36]

Liu and Shay Solomon , title =

Sayan Bhattacharya and Fabrizio Grandoni and Janardhan Kulkarni and Quanquan C. Liu and Shay Solomon , title =. 2022 , url =

work page 2022
[37]

2022 , url =

Monika Henzinger and Pan Peng , title =. 2022 , url =

work page 2022
[38]

Fully Dynamic (

Soheil Behnezhad and Rajmohan Rajaraman and Omer Wasim , editor =. Fully Dynamic (. Proceedings of the 2025 Annual. 2025 , url =

work page 2025
[39]

Round and Communication Efficient Graph Coloring , booktitle =

Yi. Round and Communication Efficient Graph Coloring , booktitle =. 2025 , url =

work page 2025
[40]

Lund, Carsten and Yannakakis, Mihalis , title =. J. Assoc. Comput. Mach. , volume =. 1994 , number =. doi:10.1145/185675.306789 , url =

work page doi:10.1145/185675.306789 1994
[41]

Combinatorica , volume =

Khanna, Sanjeev and Linial, Nathan and Safra, Shmuel , title =. Combinatorica , volume =. 2000 , number =. doi:10.1007/s004930070013 , url =

work page doi:10.1007/s004930070013 2000
[42]

arXiv preprint arXiv:2306.00171 , year =

Asymptotics for palette sparsification , author =. arXiv preprint arXiv:2306.00171 , year =

work page arXiv
[43]

arXiv preprint arXiv:2407.07928 , year =

Asymptotics for Palette Sparsification from Variable Lists , author =. arXiv preprint arXiv:2407.07928 , year =

work page arXiv
[44]

Palette Sparsification for Graphs with Sparse Neighborhoods

Palette Sparsification for Graphs with Sparse Neighborhoods , author =. arXiv preprint arXiv:2408.08256 , year =

work page arXiv
[45]

36th International Symposium on Theoretical Aspects of Computer Science,

Distributed Coloring of Graphs with an Optimal Number of Colors , author =. 36th International Symposium on Theoretical Aspects of Computer Science,. 2019 , url =

work page 2019
[46]

Bradley Baetz and David R Wood

Brooks' vertex-colouring theorem in linear time , author =. 2014 , doi =. 1401.8023 , eprinttype =

work page arXiv 2014
[47]

2013 , url =

Coloring Claw-Free Graphs with Delta-1 Colors , author =. 2013 , url =

work page 2013
[48]

Topics in Chromatic Graph Theory , pages =

Brooks' Theorem , author =. Topics in Chromatic Graph Theory , pages =. 2015 , publisher =

work page 2015
[49]

2022 , doi =

On Brooks' Theorem , author =. 2022 , doi =. 2208.02186 , eprinttype =

work page arXiv 2022
[50]

2026 , doi =

Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors , author =. 2026 , doi =. 2603.28637 , eprinttype =

work page arXiv 2026
[51]

Proceedings of the 2026 Annual

Coloring Graphs with Few Colors in the Streaming Model , author =. Proceedings of the 2026 Annual. 2026 , url =

work page 2026
[52]

Ilan Kremer and Noam Nisan and Dana Ron , title =. Comput. Complex. , volume =. 1999 , url =

work page 1999