## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, November 17, 2015, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Luis Barba (Carleton University / Université Libre de Bruxelles)

## Dynamic Graph Coloring

In this talk, we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a $C$-colorable graph undergoing four types of updates: (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 vertex 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, there is a sequence of $m$ updates on a specific graph that forces this 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.

Information for students and suggested topics for student talks