Problem 10.6: On-Line Coloring

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

More details can be found in the abstract.

September 1997, T.R. Jensen.

Back to Overview menu
Back to Graph Coloring Problems homepage

Last modified September 1, 1997 Tommy R. Jensen