On-line coloring k-colorable graphs

We show that for any k, there exists an on-line algorithm that will color any k-colorable graph on n vertices with O(n^1-1/k!) colors. This improves the previous best upper bound of O(n log ^(2k-3) n/log^(2k-4) n) due to Lovász, Saks, and Trotter. In the special cases k = 3 and k = 4 we obtain on-line algorithms that use O(n^2/3 log^{1/3 n}) and O(n^5/6 log^1/6 n) colors, respectively.