In the paper

M.M. Halldórsson and M. Szegedy, Lower Bounds for On-line
Graph Coloring, *Theoretical Computer Science* **130**,
163-174, 1994

the authors
prove a lower bound for the performance function which is better than
the bound given on
page 173 in *Graph Coloring Problems* by a factor of 2, that is,
they prove

ρ_{A}(n)
≥ 2n / (log n)^{2}

September 1997, T.R. Jensen.

Back to Graph Coloring Problems homepage