  We study a combinatorial coloring game between two players, Spoiler and
Algorithm, who alternate turns. First, Spoiler places a new token at a vertex
in $G$, and Algorithm responds by assigning a color to the new token. Algorithm
must ensure that tokens on the same or adjacent vertices receive distinct
colors. Spoiler must ensure that the token graph (in which two tokens are
adjacent if and only if their distance in $G$ is at most $1$) has chromatic
number at most $w$. Algorithm wants to minimize the number of colors used, and
Spoiler wants to force as many colors as possible. Let $f(w,G)$ be the minimum
number of colors needed in an optimal Algorithm strategy. A graph $G$ is
online-perfect if $f(w,G) = w$. We give a forbidden induced subgraph
characterization of the class of online-perfect graphs. When $G$ is not
online-perfect, determining $f(w,G)$ seems challenging; we establish $f(w,G)$
asymptotically for some (but not all) of the minimal graphs that are not
online-perfect. The game is motivated by a natural online coloring problem on
the real line which remains open.
