%0 Journal Article
%T On-line Ramsey Numbers for Paths and Stars
%A Jaroslaw Grytczuk
%A Hal Kierstead
%A Pawel Pra£¿at
%J Discrete Mathematics & Theoretical Computer Science
%D 2008
%I Discrete Mathematics & Theoretical Computer Science
%X 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.
%U http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/632