Randomized online graph coloring

N. Alon, personal communication, September 1989. Bean, 1976, Effective coloration, J. Symbolic Logic, 469, 10.2307/2272247 Blum, 1989, An O(n0.4)-approximation algorithm for 3-coloring, 535 Blum, 1990, Some tools for approximate 3-coloring, 554 M. Halldórsson and M. Szegedy, personal communication, 1991. Halldórsson, 1991, Frugal Methods for the Independent Set and Graph Coloring Problems Irani, 1990, Coloring inductive graphs on-line, 470 H. Karloff, personal communication, May 1990. Lovász, 1989, An online graph coloring algorithm with sublinear performance ratio, Discrete Math., 75, 319, 10.1016/0012-365X(89)90096-4 M. Szegedy, personal communication, March 1989. Yao, 1977, Probabilistic computations: Towards a unified measure of complexity, 222