2026-07-23T19:20:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23425 2025-10-02T12:54:46Z ddc:004 open_access

Improved Streaming Edge Coloring Chechik, Shiri Chen, Hongyi Zhang, Tianyi edge coloring streaming 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(Δ²)-edge coloring can be computed deterministically with Õ(n) space [Ansari, Saneian, and Zarrabi-Zadeh, 2022], or an O(Δ^{1.5})-edge coloring can be computed by a Õ(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 Õ(Δ^{4/3+ε}) using space Õ(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shiri Chechik and Hongyi Chen and Tianyi Zhang 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.48 urn:nbn:de:0030-drops-234257 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.48 eng https://creativecommons.org/licenses/by/4.0/legalcode