Trees with an on-line degree Ramsey number of four (Q640428)

Summary: 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 background graph. Builder's goal is to cause the background graph to contain a monochromatic copy of a given goal graph, and Painter's goal is to prevent this. In the \(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. \textit{J. Butterfield}, \textit{T. Grauman}, \textit{B. Kinnersley}, \textit{K. Milans}, \textit{C. Stocker} and \textit{D. West} [On-line Ramsey theory for bounded degree graphs. Electron. J. Comb. 18, No. 1, Research Paper P136, 17 p., electronic only (2011; Zbl 1225.05179)] previously determined all graphs \(G\) satisfying \(\mathring R_\Delta(G)\leq 3\). We provide a complete classification of trees \(T\) satisfying \(\mathring R_\Delta(T)= 4\).