Lower bounds for on-line graph colorings

Grzegorz Gutowski, Jakub Kozik, Piotr Micek, Xuding Zhu

Published 2014-04-29, updated 2015-10-09Version 2

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.