## 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. 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 Ω(N 2/ c(c−1)) vertices per update, for any constant c ≥ 2.

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

Title of host publication | Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John's, NL Canada, July 31- August 2, 2017, Proceedings |

Editors | E. Faith, A. Kolokolova, J.-R. Sack |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 97-108 |

Number of pages | 12 |

ISBN (Electronic) | 9783319621272 |

ISBN (Print) | 9783319621265 |

DOIs | |

Publication status | Published - 1 Jan 2017 |

Externally published | Yes |

Event | 15th International Symposium on Algorithms and Data Structures (WADS 2017) - Memorial University of Newfoundland, St. John’s, Canada Duration: 31 Jul 2017 → 2 Aug 2017 Conference number: 15 http://www.wads.org/ |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 10389 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 15th International Symposium on Algorithms and Data Structures (WADS 2017) |
---|---|

Abbreviated title | WADS 2017 |

Country | Canada |

City | St. John’s |

Period | 31/07/17 → 2/08/17 |

Internet address |