\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf Torsten M\"utze and Reto Sp\"ohel}
%
%
\medskip
\noindent
%
%
{\bf On the Path-Avoidance Vertex-Coloring Game}
%
%
\vskip 5mm
\noindent
%
%
%
%
For any graph $F$ and any integer $r\geq 2$, the \emph{online vertex-Ramsey density of $F$ and $r$}, denoted $m^*(F,r)$, is a parameter defined via a deterministic two-player Ramsey-type game (Painter vs.\ Builder).
This parameter was introduced in a recent paper [\textit{arXiv:1103.5849}], where it was shown
that the online vertex-Ramsey density determines the threshold of a similar probabilistic one-player game (Painter vs.\ the binomial random graph $G_{n,p}$).
For a large class of graphs $F$, including cliques, cycles, complete bipartite graphs, hypercubes, wheels, and stars of arbitrary size, a simple greedy strategy is optimal for Painter and closed formulas for $m^*(F,r)$ are known.
In this work we show that for the case where $F=P_\ell$ is a long path, the picture is very different. It is not hard to see that $m^*(P_\ell,r)= 1-1/k^*(P_\ell,r)$ for an appropriately defined integer $k^*(P_\ell,r)$, and that the greedy strategy gives a lower bound of $k^*(P_\ell,r)\geq \ell^r$. We construct and analyze Painter strategies that improve on this greedy lower bound by a factor polynomial in $\ell$, and we show that no superpolynomial improvement is possible.
\end{document}