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

10/04/2019
by   Sayan Bhattacharya, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset