Faster Dynamic $(\Delta +1)$-Coloring Against Adaptive Adversaries

Maxime Flin, Magnús M. Halldórsson

We consider the problem of maintaining a proper $(\Delta +1)$-vertex coloring in a graph on $n$-vertices and maximum degree $\Delta$ undergoing edge insertions and deletions. We give a rando…