Dynamic $(\Delta+1)$ Vertex Coloring with Adaptive Adversaries: Entropy Compression to the Rescue
We present a randomized algorithm for maintaining a $(\Delta+1)$ vertex coloring of a fully dynamic graph against an adaptive adversary with $\tilde{O}(\sqrt{n})$ amortized update time. Our algorithm improves upon the recent randomized algorithms of Behnezhad, Rajaraman, and Wasim (SODA 2025) with $\tilde{O}(n^{8/9})$...