Pith. sign in

REVIEW 3 major objections 4 minor 42 references

Improved Streaming Edge Coloring

T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A W-streaming algorithm can properly edge-color a graph in near-linear space with Δ^{4/3+ε} colors, and deterministically so for the first time.

desk verdict Genuinely new Δ^{4/3+ε} streaming edge-coloring bounds, randomized and deterministic, with a thin-but-repairable reduction lemma and one real space-bound inconsistency. read the letter →

arxiv 2504.16470 v1 pith:2SJMB4GJ submitted 2025-04-23 cs.DS

Shiri Chechik , Hongyi Chen , Tianyi Zhang This is my paper · ORCID
classification cs.DS MSC 05C1568W2068W40
keywords edgecoloringW-streamingmodelsingle-passstreamingalgorithmsrandomizedderandomizationbipartiteexpandersmultiplicitycodesnear-linearspace
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper claims that in the write-only streaming model, where a graph's edges arrive once in arbitrary order and the algorithm must emit colors as it goes, edge coloring can be done with far fewer colors than the previous quadratic and 3/2-power barriers while keeping near-linear memory. Specifically it proves a randomized algorithm using O((log Δ)^{O(1/ε)} n) space and O((log Δ)^{O(1/ε)} $Δ^{{4/3+ε}}$) colors, and a deterministic version with slightly worse polylogarithmic factors. A sympathetic reader would care because this is the first deterministic near-linear-space streaming coloring that bypasses the old O(Δ²) color bound, and it shows the bottleneck is not the output constraint but how batches of edges are organized. The insight is to color only a constant fraction of edges per pass and to recurse on the rest, while using nested random color packages indexed by batch frequencies so that unused colors around vertices can be represented compactly.

What carries the argument

The load-bearing object is a forest over the sequence of input batches whose branching factors encode how many incident edges a vertex accumulates at different time scales. On each forest, colors are allocated top-down as nested packages: a node's package is a disjoint union of the packages of its children, and the same small palette can be reused on many leaves. Each vertex keeps only the marked forest nodes that cover the batches where it previously used colors, and a random shift per low-side vertex lets most edges in a batch fall on distinct palette positions. In the high-degree regime the machinery switches to a table of palettes indexed by counters of batch appearances. For derandomization, the random shifts and package assignments are replaced by explicit unbalanced bipartite expanders from multiplicity codes, whose right-hand degree bound limits how often a palette recurs.

What would settle it

Run the boosting lemma on a graph whose edges arrive in an adversarial order and whose partial-coloring subroutine colors fewer than half the edges; if a faithful one-pass implementation must either store the uncolored edge set or read the stream again to color them all, then the O(n)-space recursion fails on that instance. Concretely, an input that is a sequence of disjoint stars or a large matching that the subroutine leaves entirely uncolored would force the recursion to revisit Ω(m) edges, which no O(n)-space single-pass algorithm can do.

Watch

Extended reading notes

Core claim

The central claim, stated as Theorem 1.1, is that for any constant ε>0 there is a randomized W-streaming algorithm that properly edge-colors any simple graph of maximum degree Δ using O((log Δ)^{O(1/ε)} n) space and O((log Δ)^{O(1/ε)} $Δ^{{4/3+ε}}$) colors in expectation; Theorem 1.2 gives a deterministic version with O((log Δ)^{O(1/ε)}(1/ε)^{O(1/$ε^{3}$)} $Δ^{{4/3+ε}}$) colors and O(n (log Δ)^{O(1/$ε^{4}$)}) space. The proof splits edges by the degrees of their endpoints inside each batch, colors the unbalanced low-degree case with a hierarchy of nested palettes over a forest of batches, uses a color-table with random shifts for the balanced high-degree case, and derandomizes both with explicit bipartite expanders built from multiplicity codes. The previously known best randomized result used O($Δ^{{1.5}}$) colors; the deterministic state of the art was O(Δ²), so the 4/3 exponent is the paper's new polynomial improvement.

Load-bearing premise

The argument assumes that the constant-fraction partial coloring can be re-run on the remaining uncolored edges within one pass by restarting the algorithm on those edges, without storing them; if the W-streaming model does not allow re-reading uncolored edges, the recursive boosting step is unsupported.

Editorial extensions

If this is right

  • Any graph with maximum degree Δ can be edge-colored in one streaming pass with near-linear memory and a palette of order Δ^{4/3+ε} colors, for every fixed ε>0.
  • The deterministic version, for the first time, breaks the quadratic Δ² color barrier in the W-streaming model without super-linear space.
  • The color count remains polynomial in Δ, not polylogarithmic, so the result is a tradeoff curve rather than a near-optimal Δ+1 coloring.
  • If the partial-coloring recursion is valid, the same boosting applies to any future algorithm that colors a constant fraction of edges, so better partial colorings immediately yield better full colorings at logarithmic color and space overhead.
  • The derandomization via multiplicity-code expanders shows that the randomness used here can be replaced without increasing space beyond polylogarithmic factors, which may transfer to other streaming coloring tasks.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same two-regime split (unbalanced versus balanced batches) might be applied to online or semi-streaming coloring, not just W-streaming, to get Δ^{4/3+ε} color bounds with sublinear memory.
  • A natural testable extension is to tune ε adaptively: since the color bound is O(Δ^{4/3+ε}), setting ε ≈ 1/log Δ gives roughly Δ^{4/3} polylog factors, and the proof suggests the constants degrade exponentially in 1/ε, so the practical break-even against Δ^{1.5} algorithms is worth benchmarking.
  • The paper leaves open whether the exponent 4/3 is an artifact of the balancing argument or a genuine barrier; a matching lower bound for one-pass W-streaming coloring with near-linear space would settle this.
  • Because the randomized algorithm's space bound holds only in expectation, a practical implementation would need tail bounds on the data structures; the deterministic theorem avoids that but at higher polylog cost.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper presents randomized and deterministic W-streaming edge-coloring algorithms for simple graphs with maximum degree Δ. The randomized algorithm (Theorem 1.1) claims O((log Δ)^{O(1/ε)} n) space and O((log Δ)^{O(1/ε)} Δ^{4/3+ε}) colors in expectation, improving the previous O(Δ^{1.5})-color randomized bound. The deterministic algorithm (Theorem 1.2) claims O((log Δ)^{O(1/ε)} (1/ε)^{O(1/ε^3)} Δ^{4/3+ε}) colors and O(n (log Δ)^{O(1/ε^4)}) space. The technical approach combines a reduction from general to bipartite graphs, a degree-pair decomposition of the input stream, forest structures over batches with nested random color packages for the low-degree case, a palette-matrix method for the regular case, and a derandomization using bipartite expanders from multiplicity codes.

Significance. If the stated bounds are correct, the randomized result is a genuine polynomial improvement over the recent Δ^{1.5} upper bound, and the deterministic result would be the first near-linear-space deterministic streaming edge coloring with substantially fewer than Δ^2 colors. The use of multiplicity-code expanders for derandomization is a technically interesting contribution that goes beyond simply replacing random shifts by expanders in a black-box way. The paper also benefits from a clean high-level architecture: isolate the unbalanced and regular cases, solve each with partial colorings, and then boost. However, several load-bearing reduction and invariant proofs are only sketched, so the manuscript is not yet at the standard of a journal publication.

major comments (3)
  1. [Section 3, Lemma 3.1] The proof of Lemma 3.1 is not a valid W-streaming construction as written. The text says to 'recursively apply the streaming algorithm on all edges marked with ⊥', but the W-streaming model allows only one pass, and uncolored edges are not re-readable unless stored, which would cost Ω(nΔ) space. The natural fix is to run O((log Δ)/δ) independent copies concurrently and feed each edge to copy i+1 only if copy i marks it ⊥, but this pipelining is not described, and the expected-fraction guarantee must be stated for arbitrary sub-instances rather than only for the original m edges. Since Lemmas 3.2 and 3.3 produce only partial colorings, Lemma 3.1 is the only mechanism in the randomized section that converts a constant-fraction coloring into a full coloring; without a complete proof of this reduction, Theorem 1.1 is not established.
  2. [Section 3.1.3, Lemma 3.7 and Invariant 3.1(2)] The proof of Invariant 3.1(2) is incomplete in the case where the highest empty node W is the root of the tree (or more generally when the coordinate f_i equals Δ^ε). The displayed argument uses minimality of f_i to assert the existence of an alternate frequency vector with coordinate f_i/2, but if f_i = Δ^ε, then f_i/2 is not an admissible branching parameter, so the inequality for node N_i is not justified. This invariant is used in Lemma 3.6 to obtain the O((log Δ)^{O(1/ε)} n) space bound, so the gap is load-bearing for Theorem 1.1. Please either repair the proof for the root/highest-node case or weaken the invariant to apply only to marked nodes and derive the space bound directly.
  3. [Theorem 1.2 vs. Lemma 4.1 and §4.2.1] The deterministic space bound in Theorem 1.2 is not directly supported by the stated lemmas. Theorem 1.2 claims O(n (log Δ)^{O(1/ε^4)}) space, but Lemma 4.1 and Lemma 4.2 provide O(n (log n)^{O(1/ε^4)}) and O(n (log n)^{O(1/ε^3)}) space respectively, and the base case in §4.2.1 uses O(n log^{200/ε^4} n) space when Δ is small. Since log n can be much larger than log Δ, the theorem's bound in terms of log Δ does not follow as written. Please clarify whether space is measured in words or bits, and either adjust the theorem statement, prove that the (log n) factors can be replaced by (log Δ) factors under the stated assumptions, or add the base-case cost explicitly to the final complexity.
minor comments (4)
  1. [Abstract and Lemma 3.2] There are several typos and duplicated phrases: the abstract has 'pa irs', and Lemma 3.2 says 'Given an graph' and repeats 'for any constant ε > 0' twice. These should be cleaned up.
  2. [Algorithm 4 (Section 4.3.2)] Line 2 of Algorithm 4 defines E_{x,y} using variables x_u and y_u that are not defined in the deterministic high-degree algorithm; this appears to be leftover from the randomized algorithm in Section 3.2. Please replace or remove this line.
  3. [Section 4.2.3, Lemma 4.10] The proof of Lemma 4.10 is omitted with the remark that it is the same as before. This is an important space bound for the deterministic construction, and the deterministic version additionally stores tuple labels on marked nodes, so a few sentences explaining why the tuple storage does not change the asymptotic space would be helpful.
  4. [Proof of Theorem 1.2] The sentence 'the total number of colors over all (l, r) would can be bounded' contains a grammatical error and should read 'can be bounded'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the central claims are built from independently stated partial-coloring lemmas and external expander constructions, not from their own conclusions.

full rationale

The paper's derivation chain is self-contained in the sense required here. Theorem 1.1 is obtained by combining Lemma 3.1 (partial-to-full coloring boosting) with Lemmas 3.2 and 3.3, each of which is a genuinely new partial-coloring subroutine with explicit algorithms, data structures, invariant proofs, and color-count calculations. No parameter is fitted to a target quantity, and no result is renamed and presented as a prediction. The only potentially self-referential ingredient is Lemma 3.1, which is attributed to the authors' own ICALP paper [CMZ24]; however, the lemma is stated and given a proof sketch in the present text, and its input is a partial-coloring algorithm A, not the full-coloring algorithm being constructed. The recursion on uncolored edges does not presuppose Theorem 1.1. The skeptic's concern that the recursive boosting is not fully specified in the W-streaming model is a proof-completeness or model-feasibility risk, not circularity: it does not make the conclusion equivalent by construction to an input. Similarly, the derandomization in Section 4 relies on the external multiplicity-code expander construction of KTS22 with stated parameters and black-box lemmas, and the deterministic theorem's bounds are calculated from those parameters rather than assumed from a prior claim of the same paper. No step reduces to a self-citation chain or to a definitional identity, so the honest finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted to data; the algorithm's constants are chosen by the user. The paper relies on several external results as building blocks, which is normal for a theory paper. The strongest dependency is the partial-coloring boosting step, which is only sketched.

assumptions (4)
  • domain assumption The general-to-bipartite reduction of GS24 (Lemma 2.1) is valid and deterministic.
    Used without proof to restrict attention to bipartite graphs; the present paper does not verify the reduction.
  • domain assumption The partial-coloring boosting lemma (Lemma 3.1, implicit in CMZ24) can be implemented in a single pass by running O(log delta) recursive copies concurrently, with space growing additively.
    This is the mechanism that converts constant-fraction coloring into full coloring; only a proof sketch is given.
  • standard math The multiplicity-code construction of KTS22 yields (K,D)-expanders with the stated expansion D = q minus a(b+2)/2 times (qK) to the 1/(b+2) for the parameter ranges used.
    Used as a black box in the derandomization; the paper states the lemma but does not prove the construction.
  • domain assumption Every input batch is a simple subgraph in the multi-to-simple reduction (Lemma 4.17), and that reduction preserves the W-streaming model.
    The extension to multigraphs relies on this reduction, which is proved but adds logarithmic factors.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Streaming Edge Coloring." pith.science (2026). https://pith.science/paper/2SJMB4GJ

@misc{pith2026250416470,
  author       = {Pith},
  title        = {Pith review of: Improved Streaming Edge Coloring},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2SJMB4GJ}},
  note         = {Machine review of arXiv:2504.16470}
}
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 $\Delta$, it is known that in the W-streaming model, an $O(\Delta^2)$-edge coloring can be computed deterministically with $\tilde{O}(n)$ space [Ansari, Saneian, and Zarrabi-Zadeh, 2022], or an $O(\Delta^{1.5})$-edge coloring can be computed by a $\tilde{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 $\tilde{O}(\Delta^{4/3+\epsilon})$ using space $\tilde{O}(n)$ deterministically, for any constant $\epsilon > 0$. This is the first deterministic result that bypasses the quadratic bound on the number of colors while using near-linear space.

Figures

Figures reproduced from arXiv: 2504.16470 by the authors.

Figure 1
Figure 1. In this picture, it shows an example of a forest [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 38 canonical work pages

  1. [1]

    Vizing's theorem in near-linear time

    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

    work page arXiv 2024

  2. [2]

    An efficient algorithm for colouring the edges of a graph with +1 colours

    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

    work page 1982

  3. [3]

    Faster Vizing and Near-Vizing Edge Coloring Algorithms

    Sepehr Assadi. Faster Vizing and Near-Vizing Edge Coloring Algorithms . In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2025

    work page 2025

  4. [4]

    Simple streaming algorithms for edge coloring

    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 \"u r Informatik, 2022

    work page 2022

  5. [5]

    Distributed edge coloring in time polylogarithmic in

    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

    work page 2022

  6. [6]

    Faster ( +1) -Edge Coloring: Breaking the m n Time Barrier

    Sayan Bhattacharya, Din Carmon, Mart \' n Costa, Shay Solomon, and Tianyi Zhang. Faster ( +1) -Edge Coloring: Breaking the m n Time Barrier . In 65th IEEE Symposium on Foundations of Computer Science (FOCS) , 2024

    work page 2024

  7. [7]

    Dynamic Algorithms for Graph Coloring

    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

    work page 2018

  8. [8]

    Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time

    Sayan Bhattacharya, Mart\'in 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

    work page 2024

Show all 42 references
  1. [9]

    Even Faster ( +1) -Edge Coloring via Shorter Multi-Step Vizing Chains

    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)

    2025

  2. [10]

    Streaming and massively parallel algorithms for edge coloring

    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 fuer Informatik, 2019

    2019

  3. [11]

    A fast distributed algorithm for ( +1) -edge-coloring

    Anton Bernshteyn. A fast distributed algorithm for ( +1) -edge-coloring . J. Comb. Theory, Ser. B , 152:319--352, 2022

    2022

  4. [12]

    Online edge coloring algorithms via the nibble method

    Sayan Bhattacharya, Fabrizio Grandoni, and David Wajc. Online edge coloring algorithms via the nibble method. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2830--2842. SIAM , 2021

    2021

  5. [13]

    Fully-dynamic graph algorithms with sublinear time inspired by distributed computing

    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

    2017

  6. [14]

    Online edge coloring is (nearly) as easy as offline

    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

    2024

  7. [15]

    Deterministic Online Bipartite Edge Coloring

    Joakim Blikstad, Ola Svensson, Radu Vintan, and David Wajc. Deterministic Online Bipartite Edge Coloring . In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2025

    2025

  8. [16]

    Distributed Edge Coloring and a Special Case of the Constructive Lov \' a sz Local Lemma

    Yi - Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto. Distributed Edge Coloring and a Special Case of the Constructive Lov \' a sz Local Lemma . ACM Trans. Algorithms , 16(1):8:1--8:51, 2020

    2020

  9. [17]

    The Power of Multi-step Vizing Chains

    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

    2023

  10. [18]

    Aleksander B. G. Christiansen. Deterministic dynamic edge-colouring. CoRR , abs/2402.13139, 2024

    2024

  11. [19]

    Improved algorithms for edge colouring in the w-streaming model

    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

    2021

  12. [20]

    Streaming Edge Coloring with Subquadratic Palette Size

    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...

    2024

  13. [21]

    Edge-coloring bipartite multigraphs in o (e logd) time

    Richard Cole, Kirstin Ost, and Stefan Schirra. Edge-coloring bipartite multigraphs in o (e logd) time. Combinatorica , 21(1):5--12, 2001

    2001

  14. [22]

    Tight bounds for online edge coloring

    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

    2019

  15. [23]

    Improved distributed algorithms for the lov \' a sz local lemma and edge coloring

    Peter Davies. Improved distributed algorithms for the lov \' a sz local lemma and edge coloring. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 4273--4295. SIAM , 2023

    2023

  16. [24]

    Trading off space for passes in graph streaming problems

    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

    2009

  17. [25]

    Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs

    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

    2025

  18. [26]

    Dynamic edge coloring with improved approximation

    Ran Duan, Haoqing He, and Tianyi Zhang. Dynamic edge coloring with improved approximation. In 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2019

    2019

  19. [27]

    (2 - 1) -Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting

    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

    2014

  20. [28]

    Deterministic distributed edge-coloring via hypergraph maximal matching

    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

    2017

  21. [29]

    Deterministic distributed edge-coloring with fewer colors

    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

    2018

  22. [30]

    Algorithms for edge coloring

    Harold N Gabow, Takao Nishizeki, Oded Kariv, Daneil Leven, and Osamu Terada. Algorithms for edge coloring. Technical Rport , 1985

    1985

  23. [31]

    Low-memory algorithms for online edge coloring

    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 \"u r Informatik, 2024

    2024

  24. [32]

    Finding euler tours in one pass in the w-streaming model with o (n log (n)) ram

    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

    2017 arXiv

  25. [33]

    Unbalanced expanders and randomness extractors from parvaresh--vardy codes

    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

    2009

  26. [34]

    Liu, Ashwin Sah, Mehtaab Sawhney, and Jakub Tarnawski

    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

    2022

  27. [35]

    Unbalanced expanders from multiplicity codes

    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 \"u r Informatik, 2022

    2022

  28. [36]

    Some simple distributed algorithms for sparse networks

    Alessandro Panconesi and Romeo Rizzi. Some simple distributed algorithms for sparse networks. Distributed computing , 14(2):97--100, 2001

    2001

  29. [37]

    Streaming edge coloring with asymptotically optimal colors

    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 Dags...

    2024

  30. [38]

    A theorem on coloring the lines of a network

    Claude E Shannon. A theorem on coloring the lines of a network. Journal of Mathematics and Physics , 28(1-4):148--152, 1949

    1949

  31. [39]

    Fast and simple edge-coloring algorithms

    Corwin Sinnamon. Fast and simple edge-coloring algorithms. arXiv preprint arXiv:1907.03201 , 2019

    1907 arXiv

  32. [40]

    The greedy algorithm is not optimal for on-line edge coloring

    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

    2021

  33. [41]

    Loss-less condensers, unbalanced expanders, and extractors

    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

    2001

  34. [42]

    The chromatic class of a multigraph

    Vadim G Vizing. The chromatic class of a multigraph. Cybernetics , 1(3):32--41, 1965

    1965

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.