Beyond Brooks: $(\hat{I}”-1)$-Coloring in Semi-Streaming

Abstract

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

34 pages, accepted for publication at ICALP 2026