PhD Seminar • Algorithms and Complexity • Δ-coloring in Graph Streams I

Please note: This PhD seminar will take place in DC 2568.

Parth Mittal, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Sepehr Assadi

Brooks’ Theorem states that a graph with maximum degree Δ can be colored with Δ colors as long as it is not a clique or an odd-cycle. In this talk I will give an overview of our result showing a 1-pass, O(n poly log n) space streaming algorithm that computes a Δ-coloring of a graph given as an edge stream.

Based on joint work with Sepehr Assadi and Pankaj Kumar.