Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $\Delta$-Coloring

Sepehr Assadi, Pankaj Kumar, Parth Mittal

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…