We design fast dynamic algorithms for proper vertex and edge colorings in a graph undergoing edge insertions and deletions. In the static setting, there are simple linear time algorithms for (∆ + 1)-vertex coloring and (2∆ − 1)-edge coloring in a graph with maximum degree ∆. It is natural to ask if we can efficiently maintain such colorings in the dynamic setting as well. We get the following three results. (1) We present a randomized algorithm which maintains a (∆ + 1)-vertex coloring with O(log ∆) expected amortized update time. (2) We present a deterministic algorithm which maintains a (1 + o (1)
Bhattacharya et al. REF gave a randomized algorithm that maintains a (∆ + 1)-coloring with O(log ∆) expected amortized update time and a deterministic algorithm that maintains a (∆ + o(∆))-coloring with O(polylog ∆) amortized update time.
D S ] 1 2 N ov 2 01 7 Dynamic Algorithms for Graph Coloring