<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\magnification=1200
\hsize=4in
\nopagenumbers
\noindent
 {\bf M. M. Halld\' orsson }
\medskip
\noindent {\bf Online Coloring Known Graphs} \vskip.5cm

The problem of online coloring an unknown graph is known to be
hard. Here we consider the problem of online coloring in the
relaxed situation where the input must be isomorphic to a given
known graph. All that foils a computationally powerful player is
that it is not known to which sections of the graph the vertices
to be colored belong. We show that the performance ratio of any
online coloring algorithm with {\it advance knowledge of the input
graph} is at least $\Omega(N/\log^2 N)$, where $N$ is the number
of vertices. This matches and generalizes the bound for the case
of an unknown input graph. We also show that any online
independent set algorithm has a performance ratio at least $N/8$.

\bye
</pre></body></html>