Beyond Brooks: $(\mathrm{\Delta }-1)$-Coloring in Semi-Streaming

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