Dynamic Algorithms for Graph Coloring

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))Δ$-vertex coloring with $O(\text{poly} \log Δ)$ amortized update time. (3) We present a simple, deterministic algorithm which maintains a $(2Δ-1)$-edge coloring with $O(\log Δ)$ worst-case update time. This improves the recent $O(Δ)$-edge coloring algorithm with $\tilde{O}(\sqrtΔ)$ worst-case update time by Barenboim and Maimon.