Multicolor on-line degree Ramsey numbers of trees

In the on-line Ramsey game on a family $H$ of graphs, “Builder”presents edges of a graph one-by-one, and “Painter” colors each edge as it ispresented; we require that Builder keep the presented graph in $H$.Builder wins the game $(G, H)$ if Builder can ensure that amonochromatic $G$ arises. The {\em $s$-color on-line degree Ramsey number of$G$}, denoted $\odr(G;s)$, is the least $k$ such that Builder wins$(G,H)$ when $H$ is the family of graphs having maximum degree atmost $k$ and Painter has $s$ colors available. More generally,$\odr(G_1, \ldots, G_s)$ is the minimum $k$ such that Builder can force a copyof $G_i$ in color $i$ for some $i$ when restricted to graphs with maximumdegree at most $k$.

In this paper, we prove that $\odr(T; s) \le s(\Delta(T) - 1) + 1$ for everytree $T$; this is sharp, with equality whenever $T$ has adjacent vertices ofmaximum degree. We also give lower and upper bounds on$\odr(G_1, \dots, G_s)$ when each $G_i$ is a double-star. When each $G_i$ isa star, we determine $\odr(G_1, \dots, G_s)$ exactly.

Full Text (PDF format)

Published 11 September 2012