Parth Mittal: Brooks’ Theorem in Graph Streams

Zoom Passcode: 319645

Abstract:
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: there exists a randomized
algorithm that with high probability finds a (Delta+1)-coloring of the input
graph in only O(n polylog n) space assuming a single pass over the edges of
the graph in any arbitrary order.
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?

In this talk, I will describe a semi-streaming algorithm to find a
Delta-coloring, namely, prove a “Streaming Brooks’ Theorem”.

Based on joint work with Sepehr Assadi and Pankaj Kumar, to appear in STOC 2022.