  Every graph with maximum degree $\Delta$ can be colored with $(\Delta+1)$
colors using a simple greedy algorithm. Remarkably, recent work has shown that
one can find such a coloring even in the semi-streaming model. But, in reality,
one almost never needs $(\Delta+1)$ colors to properly color a graph. Indeed,
the celebrated \Brooks' theorem states that every (connected) graph beside
cliques and odd cycles can be colored with $\Delta$ colors. Can we find a
$\Delta$-coloring in the semi-streaming model as well?
  We settle this key question in the affirmative by designing a randomized
semi-streaming algorithm that given any graph, with high probability, either
correctly declares that the graph is not $\Delta$-colorable or outputs a
$\Delta$-coloring of the graph.
  The proof of this result starts with a detour. We first (provably) identify
the extent to which the previous approaches for streaming coloring fail for
$\Delta$-coloring: for instance, all these approaches can handle streams with
repeated edges and they can run in $o(n^2)$ time -- we prove that neither of
these tasks is possible for $\Delta$-coloring. These impossibility results
however pinpoint exactly what is missing from prior approaches when it comes to
$\Delta$-coloring.
  We then build on these insights to design a semi-streaming algorithm that
uses $(i)$ a novel sparse-recovery approach based on sparse-dense
decompositions to (partially) recover the "problematic" subgraphs of the input
-- the ones that form the basis of our impossibility results -- and $(ii)$ a
new coloring approach for these subgraphs that allows for recoloring of other
vertices in a controlled way without relying on local explorations or finding
"augmenting paths" that are generally impossible for semi-streaming algorithms.
We believe both these techniques can be of independent interest.
