Lower bounds for on-line graph coloring

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.