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)

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(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
PublisherSpringer
Pages97-108
Number of pages12
ISBN (Electronic)9783319621272
ISBN (Print)9783319621265
DOIs
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
http://www.wads.org/

Publication series

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

Conference

Conference15th International Symposium on Algorithms and Data Structures (WADS 2017)
Abbreviated titleWADS 2017
CountryCanada
CitySt. John’s
Period31/07/172/08/17
Internet address

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

Cite this