#### Theory Seminar

# Parth Mittal: Brooks’ Theorem in Graph Streams

This event is free and open to the publicAdd to Google Calendar

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.