On-line Ramsey Numbers for Paths and Stars
Jaroslaw Grytczuk, Hal Kierstead, Pawel Prałat
Abstract
We study on-line version of size-Ramsey numbers of graphs defined via
a
game played between Builder and Painter: in one round Builder joins
two
vertices by an edge and Painter paints it red or blue. The goal of
Builder
is to force Painter to create a monochromatic copy of a fixed graph
H
in as few rounds as possible. The minimum number of rounds (assuming
both
players play perfectly) is the on-line Ramsey number
r(H)
of the graph H. We determine exact values of
r(H)
for a few short paths and obtain a general upper bound
r(Pn)≤4n-7.
We also study asymmetric version of this parameter when one of the
target
graphs is a star Sn with n edges.
We
prove that r(Sn,H)≤n
·e(H) when H is any tree, cycle or clique.
Full Text: PDF PostScript