Lower bounds for on-line graph coloring

Magnus M. Halldórsson, Mario Szegedy

Research output: Contribution to journalArticlepeer-review

38 Scopus citations

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 considered. We show that for every such algorithm there exists a log n-colorable graph for which the algorithm uses at least 2n/log n colors. This also holds for randomized algorithms, to within a constant factor, against an oblivious adversary. We then show that various means of relaxing the constraints of the on-line model do not reduce these lower bounds. The features include presenting the input in blocks of up to log2 n vertices, recoloring any fraction of the vertices, presorting vertices by degree, and disclosing the adversary's previous coloring.

Original languageEnglish (US)
Pages (from-to)163-174
Number of pages12
JournalTheoretical Computer Science
Volume130
Issue number1
DOIs
StatePublished - Aug 1 1994

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Lower bounds for on-line graph coloring'. Together they form a unique fingerprint.

Cite this