Multicolor on-line degree Ramsey numbers of trees (Q353401)

The \(s\)-color on-line degree Ramsey number of \(G\), denoted \(\dot{R}_\Delta(G;s)\), is the minimum \(k\) such that in any on-line coloring with \(s\) colors on graphs with maximum degree at most \(k\), there is a monochromatic copy of \(G\). It is shown that \(\dot{R}_\Delta(T;s) \leq s(\Delta(T) - 1) + 1\) for every tree \(T\). The inequality is sharp, and for trees with adjacent vertices of maximum degree it is precise. Various upper and lower bounds are given for special trees such as stars and double stars. Also, the on-line degree Ramsey numbers \(\dot{R}_\Delta(G_1, G_2, \dots, G_s)\) where the \(G_i\) are paths and special trees are determined.