2026-07-20T05:37:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26445 2026-07-01T07:16:11Z ddc:004 open_access

Faster Deterministic Streaming Vertex Coloring Chechik, Shiri Chen, Hongyi Zhang, Tianyi vertex coloring streaming Graph coloring is a fundamental problem in computer science. In the semi-streaming model, an input graph G on n vertices and maximum degree Δ is presented as a stream of edges, and the goal is to compute a vertex coloring using a small number of colors while storing only Õ(n) bits of memory. Recent work has revealed an exponential separation between randomized and deterministic approaches in this setting: while randomized algorithms can achieve a (Δ+1)-coloring in a single pass [Assadi, Chen, and Khanna, 2019], any single-pass deterministic algorithm requires exp(Δ^Ω(1)) colors [Assadi, Chen, and Sun, 2022]. Consequently, deterministic algorithms that use few colors must necessarily make multiple passes over the stream. Prior to this work, the best known deterministic trade-offs were: an O(Δ²)-coloring in 2 passes, an O(Δ)-coloring in O(log Δ) passes [Assadi, Chen, and Sun, 2022], and a (Δ+1)-coloring in O(log Δ ⋅ log log Δ) passes [Assadi, Chakrabarti, Ghosh, and Stoeckl, 2023]. It remained open whether better trade-offs - particularly with sub-logarithmic pass complexity and linear-in-Δ palette size - were achievable. In this paper, we present a new deterministic semi-streaming algorithm that computes an O(Δ)-coloring in O(√{log Δ}) passes. This is the first deterministic streaming algorithm to achieve a coloring with palette size linear-in-Δ using sublogarithmic-in-Δ passes. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shiri Chechik and Hongyi Chen and Tianyi Zhang 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.56 urn:nbn:de:0030-drops-264453 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.56 eng https://creativecommons.org/licenses/by/4.0/legalcode