Dynamic Algorithms for Graph Coloring

Abstract

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

To appear in SODA 2018