Jaehyun Koo (구재현), Dynamic Graph Coloring: Sequential, Parallel, and Distributed
For any graph with maximum degree at most $\Delta$, a simple inductive argument shows that the graph can be properly colored using $\Delta+1$ colors. However, a direct implementation of this argument is highly sequential, motivating extensive research into efficient algorithms in parallel, distributed, and dynamic settings. In this talk, I will present a simple randomized …