Improved Dynamic Graph Coloring

Understand

This paper studies the fundamental problem of graph coloring in fully dynamic graphs.

• Since the problem of computing an optimal coloring, or even approximating it to within $n^{1-\epsilon}$ for any $\epsilon > 0$, is NP-hard in static graphs, there is no hope to achieve any meaningful computational results for general graphs in the dynamic setting.
• It is therefore only natural to consider the combinatorial aspects of dynamic coloring, or alternatively, study restricted families of graphs.
• Towards understanding the combinatorial aspects of this problem, one may assume a black-box access to a static algorithm for $C$-coloring any subgraph of the dynamic graph, and investigate the trade-off between the number of colors and the number of recolorings per update step.