Dynamic graph coloring

Luis Barba, Jean Cardinal, Matias Korman, Stefan Langerman, André van Renssen, Marcel Roeloffzen, Sander Verdonschot

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

13 Citations (Scopus)


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(CdN1/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(dN1/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 languageEnglish
Title of host publicationAlgorithms and Data Structures - 15th International Symposium, WADS 2017, St. John's, NL Canada, July 31- August 2, 2017, Proceedings
EditorsE. Faith, A. Kolokolova, J.-R. Sack
Place of PublicationBerlin
Number of pages12
ISBN (Electronic)9783319621272
ISBN (Print)9783319621265
Publication statusPublished - 1 Jan 2017
Externally publishedYes
Event15th International Symposium on Algorithms and Data Structures (WADS 2017) - Memorial University of Newfoundland, St. John’s, Canada
Duration: 31 Jul 20172 Aug 2017
Conference number: 15

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference15th International Symposium on Algorithms and Data Structures (WADS 2017)
Abbreviated titleWADS 2017
CitySt. John’s
Internet address

Fingerprint Dive into the research topics of 'Dynamic graph coloring'. Together they form a unique fingerprint.

Cite this