LOWER BOUNDS FOR ONLINE GRAPH-COLORING

Citation
Mm. Halldorsson et M. Szegedy, LOWER BOUNDS FOR ONLINE GRAPH-COLORING, Theoretical computer science, 130(1), 1994, pp. 163-174
Citations number
16
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
ISSN journal
03043975
Volume
130
Issue
1
Year of publication
1994
Pages
163 - 174
Database
ISI
SICI code
0304-3975(1994)130:1<163:LBFOG>2.0.ZU;2-N
Abstract
An algorithm for vertex-coloring graphs is said to be on-line if each vertex is irrevocably assigned a color before later vertices are consi dered. We show that for every such algorithm there exists a log n-colo rable graph for which the algorithm uses at least 2n/log n colors. Thi s also holds for randomized algorithms, to within a constant factor, a gainst an oblivious adversary. We then show that various means of rela xing the constraints of the on-line model do not reduce these lower bo unds. The features include presenting the input in blocks of up to log 2 n vertices, recoloring any fraction of the vertices, presorting vert ices by degree, and disclosing the adversary's previous coloring.