Multicolor on-line degree Ramsey numbers of trees. (English) Zbl 1274.05317

Kinnersley, William B.; West, Douglas B.

J. Comb. 3, No. 1, 91-100 (2012).

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.

Reviewer: Ralph Faudree (Memphis)

MSC:

05C55	Generalized Ramsey theory
05C05	Trees
05C57	Games on graphs (graph-theoretic aspects)

Keywords:

Ramsey numbers; degree; on-line coloring; trees