\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}

\begin{document}
\noindent
%
%
{\bf Jane Butterfield, Tracy Grauman, William B. Kinnersley, Kevin G. Milans, Christopher Stocker and Douglas B. West }
%
%

\medskip
\noindent
%
%
{\bf On-line Ramsey Theory for Bounded Degree Graphs}
%
%

\vskip 5mm
\noindent
%
%
%
%
When graph Ramsey theory is viewed as a game, ``Painter'' 2-colors the
edges of a graph presented by ``Builder''.  Builder wins if every
coloring has a monochromatic copy of a fixed graph $G$.  In the
on-line version, iteratively, Builder presents one edge and Painter
must color it.  Builder must keep the presented graph in a class
${\cal H}$.  Builder wins the game $(G,{\cal H})$ if a monochromatic
copy of $G$ can be forced.  The {\it on-line degree Ramsey number}
$\mathaccent"017{R}_\Delta(G)$ is the least $k$ such that Builder wins
$(G,{\cal H})$ when ${\mathcal H}$ is the class of graphs with maximum
degree at most $k$.
Our results include:\\
1) $\mathaccent"017{R}_\Delta(G)\!\le\!3$ if and only if $G$ is a linear forest or each component lies inside $K_{1,3}$.\\
2) $\mathaccent"017{R}_\Delta(G)\ge \Delta(G)+t-1$, where $t=\max_{uv\in E(G)}\min\{d(u),d(v)\}$.\\
3) $\mathaccent"017{R}_\Delta(G)\le d_1+d_2-1$ for a tree $G$, where $d_1$ and $d_2$ are two largest vertex degrees.\\
4) $4\le \mathaccent"017{R}_\Delta(C_n)\le 5$, with $\mathaccent"017{R}_\Delta(C_n)=4$ except for finitely many odd values of $n$.\\
5) $\mathaccent"017{R}_\Delta(G)\le6$ when $\Delta(G)\le 2$.  

The lower bounds come from strategies for Painter that color edges red whenever
the red graph remains in a specified class.  The upper bounds use a result
showing that Builder may assume that Painter plays ``consistently''.

\end{document}

.