Fully Dynamic (\Delta+1) Coloring Against Adaptive Adversaries
Fully Dynamic (\Delta+1) Coloring Against Adaptive Adversaries
Over the years, there has been extensive work on fully dynamic algorithms for classic graph problems that admit greedy solutions. Examples include $(\Delta+1)$ vertex coloring, maximal independent set, and maximal matching. For all three problems, there are randomized algorithms that maintain a valid solution after each edge insertion or deletion …