Lower bounds for on-line graph colorings

Abstract

We propose two strategies for Presenter in on-line graph coloring games. The first one constructs bipartite graphs and forces any on-line coloring algorithm to use $2{\log }_{2}n-10$ colors, where $n$ is the number of vertices in the constructed graph. This is best possible up to an additive constant. The second strategy constructs graphs that contain neither $C_3$ nor $C_5$ as a subgraph and forces $\Omega ({\frac{n}{\log n}}^{\frac{1}{3}})$ colors. The best known on-line coloring algorithm for these graphs uses $O(n^{\frac{1}{2}})$ colors.