2026-09-08T02:21:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26481 2026-09-05T19:45:10Z ddc:004 open_access

Beyond Brooks: (Δ-1)-Coloring in Semi-Streaming Flin, Maxime Halldórsson, Magnús M. Graph coloring streaming algorithm Reed [J. Comb. Theory B, 1999] showed that graphs of maximum degree Δ ⩾ 10^14 without Δ-cliques are (Δ-1)-colorable. We design a one-pass semi-streaming algorithm for computing such a coloring. Additionally, we prove that any one-pass (Δ-k)-coloring algorithm for 0 ⩽ k < (Δ+1)/2 requires Ω(n(k+1)) space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Maxime Flin and Magnús M. Halldórsson 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.92 urn:nbn:de:0030-drops-264817 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.92 eng https://creativecommons.org/licenses/by/4.0/legalcode