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 …