In this talk, we study the number of vertex recolorings that an algorithms needs to perform in order to maintain a proper coloring of a $C$-colorable graph under four types of update: (i) delete an edge; (ii) insert an edge; (iii) delete a vertex and all incident edges; or (iv) insert a vertex with a set of incident edges. We assume that all updates keep the graph $C$-colorable and that $N$ is the maximum number of vertices in the graph at any point in time.

We present two algorithms to maintain an approximation of the optimal coloring that, together, present a trade-off between the number of recolorings and the number of colors used to color the graph: For any $d>0$, the first algorithm maintains a proper $O(C d N^{1/d})$-coloring and recolors at most $O(d)$ vertices per update. The second maintains an $O(C d)$-coloring using $O(dN^{1/d})$ recolorings per update. Both algorithms achieve the same asymptotic performance when $d = \log N$.

Moreover, we show that for any algorithm that maintains a $c$-coloring of a $2$-colorable graph on $N$ vertices during a sequence of $m$ updates, there is a sequence of updates that forces the algorithm to recolor at least $\Omega(m\cdot N^\frac{2}{c(c-1)})$ vertices.

This is joint work with Jean Cardinal, Matias Korman, Stefan Langerman, André van Renssen, Marcel Roeloffzen and Sander Verdonschot.