On-line Ramsey theory for bounded degree graphs (Q551227)

Summary: 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 \({\mathcal H}\). Builder wins the game \((G,{\mathcal H})\) if a monochromatic copy of \(G\) can be forced. The on-line degree Ramsey number \({\overset{\scriptscriptstyle\circ} R}_\Delta(G)\) is the least \(k\) such that Builder wins \((G,{\mathcal H})\) when \({\mathcal H}\) is the class of graphs with maximum degree at most \(k\). Our results include: {\parindent=5mm \begin{itemize}\item[1)]\({\overset{\scriptscriptstyle\circ} R}_\Delta(G)\leq 3\) if and only if \(G\) is a linear forest or each component lies inside \(K_{1,3}\). \item[2)]\({\overset{\scriptscriptstyle\circ} R}_\Delta(G)\geq\Delta(G)+ t- 1\), where \(t= \max_{uv\in E(G)}\min\{d(u), d(v)\}\). \item[3)]\({\overset{\scriptscriptstyle\circ} \Delta}(G)\leq d_1+ d_2- 1\) for a tree \(G\), where \(d_1\) and \(d_2\) are two largest vertex degrees. \item[4)]\(4\leq{\overset{\scriptscriptstyle\circ}\Delta}(C_n)\leq 5\), with \({\overset{\scriptscriptstyle\circ} R}_\Delta(C_n)= 4\) except for finitely many odd values of \(n\). \item[5)]\({\overset{\scriptscriptstyle\circ} R}_\Delta(G)\leq 6\) when \(\Delta(G)\leq 2\). \end{itemize}} 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''.