Dynamic Graph Coloring
OPEN ACCESS
Author / Producer
Date
2019-04
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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. The two converge when d=logN, maintaining an O(ClogN)-coloring with O(logN) 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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
81 (4)
Pages / Article No.
1319 - 1341
Publisher
Springer
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Dynamic coloring; Graphs; Data structures; Amortized algorithms
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)