Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring

Every graph with maximum degree Δ can be colored with (Δ + 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: there exists a randomized algorithm that with high probability finds a (Δ + 1)-coloring of the input graph in only 𝑂(𝑛 • polylog 𝑛) space assuming a single pass over the edges of the graph in any arbitrary order. But, in reality, one almost never needs (Δ + 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 Δ colors. Can we find a Δ-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 Δ-colorable or outputs a Δ-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 Δ-coloring: for instance, all these prior approaches can handle streams with repeated edges and they can run in 𝑜(𝑛 2 ) time, whereas An extended abstract of this paper appeared in ACM Symposium on Theory of Computing (STOC'22) [8] .