Title: Tight Bounds for Online Coloring of Basic Graph Classes,
Abstract: We resolve a number of long-standing open problems in online graph coloring.
More specifically, we develop tight lower bounds on the performance of online
algorithms for fundamental graph classes. An important contribution is that our
bounds also hold for randomized online algorithms, for which hardly any results
were known. Technically, we construct lower bounds for chordal graphs. The
constructions then allow us to derive results on the performance of randomized
online algorithms for the following further graph classes: trees, planar,
bipartite, inductive, bounded-treewidth and disk graphs. It shows that the best
competitive ratio of both deterministic and randomized online algorithms is
$\Theta(\log n)$, where $n$ is the number of vertices of a graph. Furthermore,
we prove that this guarantee cannot be improved if an online algorithm has a
lookahead of size $O(n/\log n)$ or access to a reordering buffer of size
$n^{1-\epsilon}$, for any $0<\epsilon\leq 1$. A consequence of our results is
that, for all of the above mentioned graph classes except bipartite graphs, the
natural $\textit{First Fit}$ coloring algorithm achieves an optimal
performance, up to constant factors, among deterministic and randomized online
algorithms.