Fully Dynamic $(Δ+1)$-Coloring in Constant Update Time

The problem of (vertex) $(Δ+1)$-coloring a graph of maximum degree $Δ$ has been extremely well-studied over the years in various settings and models. Surprisingly, for the dynamic setting, almost nothing was known until recently. In SODA'18, Bhattacharya, Chakrabarty, Henzinger and Nanongkai devised a randomized data structure for maintaining a $(Δ+1)$-coloring with $O(\log Δ)$ expected amortized update time. In this paper, we present a $(Δ+1)$-coloring data structure that achieves a constant amortized update time and show that this time bound holds not only in expectation but also with high probability.