\documentclass[12pt]{article} \usepackage{amsmath,mathrsfs,bbm} \usepackage{amssymb} \textwidth=4.825in \overfullrule=0pt \thispagestyle{empty} \begin{document} \noindent % % {\bf David Rolnick } % % \medskip \noindent % % {\bf Trees with an On-Line Degree Ramsey Number of Four} % % \vskip 5mm \noindent % % % % On-line Ramsey theory studies a graph-building game between two players. The player called Builder builds edges one at a time, and the player called Painter paints each new edge red or blue after it is built. The graph constructed is called the \emph{background graph}. Builder's goal is to cause the background graph to contain a monochromatic copy of a given \emph{goal graph}, and Painter's goal is to prevent this. In the \emph{$S_k$-game} variant of the typical game, the background graph is constrained to have maximum degree no greater than $k$. The on-line degree Ramsey number $\mathring{R}_{\Delta}(G)$ of a graph $G$ is the minimum $k$ such that Builder wins an $S_k$-game in which $G$ is the goal graph. Butterfield et al. previously determined all graphs $G$ satisfying $\mathring{R}_{\Delta}(G)\le 3$. We provide a complete classification of trees $T$ satisfying $\mathring{R}_{\Delta}(T)=4$. \end{document}