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.