Parallel Batch Dynamic Vertex Coloring in $O(\log \mathrm{\Delta })$ Amortized Update Time

We present the first parallel batch-dynamic algorithm for maintaining a proper $(\mathrm{\Delta }+1)$-vertex coloring. Our approach builds on a new sequential dynamic algorithm inspired by the work of Bhattacharya et al. (SODA’18). The resulting randomized algorithm achieves $O(\log \mathrm{\Delta })$ expected amortized update time and, for any batch of $b$ updates, has parallel span $O(\mathrm{polylog}b+\mathrm{polylog}n)$ with high probability.