Lower bounds for on-line graph coloring

Abstract

An algorithm for vertex-coloring graphs is said to be online if each vertex is irrevocably assigned a color before any later vertices are considered. We show that such algorithms are inherently ineffective. The performance ratio of any such algorithm can be no better than Ω(n/log2n), even for randomized algorithms against oblivious adversary. We also 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 log2 n vertices, recoloring any fraction of the vertices, presorting vertices according to degree, and disclosing the adversary's previous coloring.