## Abstract

In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a graph under insertion and deletion of vertices and edges. We present two algorithms that achieve different trade-offs between the number of recolorings and the number of colors used. For any d> 0 , the first algorithm maintains a proper O(CdN
^{1}
^{/}
^{d} ) -coloring while recoloring at most O(d) vertices per update, where C and N are the maximum chromatic number and maximum number of vertices, respectively. The second algorithm reverses the trade-off, maintaining an O(Cd) -coloring with O(dN
^{1}
^{/}
^{d} ) recolorings per update. The two converge when d= log N, maintaining an O(Clog N) -coloring with O(log N) recolorings per update. We also present a lower bound, showing that any algorithm that maintains a c-coloring of a 2-colorable graph on N vertices must recolor at least Ω(N2c(c-1)) vertices per update, for any constant c≥ 2.

Original language | English |
---|---|

Pages (from-to) | 1319-1341 |

Number of pages | 23 |

Journal | Algorithmica |

Volume | 81 |

Issue number | 4 |

DOIs | |

Publication status | Published - Apr 2019 |

## Keywords

- Amortized algorithms
- Data structures
- Dynamic coloring
- Graphs