Beyond Brooks: $(Δ-1)$-Coloring in Semi-Streaming

For graph coloring in the streaming model, this work provides the first algorithm for a non-trivial coloring beyond Brooks' theorem and establishes a tight space lower bound for a range of coloring parameters.

The paper presents the first one-pass semi-streaming algorithm for $(Δ-1)$-coloring graphs with maximum degree $Δ\\geq 10^{14}$ and no $Δ$-cliques, and proves a space lower bound of $Ω(n(k+1))$ for any one-pass $(Δ-k)$-coloring algorithm for $0\\leq k < (Δ+1)/2$.