×

zbMATH — the first resource for mathematics

Multicolor on-line degree Ramsey numbers of trees. (English) Zbl 1274.05317
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.

MSC:
05C55 Generalized Ramsey theory
05C05 Trees
05C57 Games on graphs (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI