Lower Bounds for On-line Graph Coloring

Magnús M. Halldórsson
Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.

Mario Szegedy
ATT Bell Laboratories

Abstract: An algorithm for vertex-coloring graphs is said to be {\em 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 \vn{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 $\log^2 n$ vertices, recoloring any fraction of the vertices, presorting vertices by degree, and disclosing the adversary's previous coloring.