J. A. Grytczuk ; H. A. Kierstead ; P. Prałat - On-line Ramsey numbers for paths and stars

dmtcs:427 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, Vol. 10 no. 3 - https://doi.org/10.46298/dmtcs.427
On-line Ramsey numbers for paths and starsArticle

Authors: J. A. Grytczuk 1; H. A. Kierstead 2; P. Prałat 3

  • 1 Theoretical Computer Science Department [Krakow]
  • 2 Department of Mathematics and Statistics [Tempe, Arizona]
  • 3 Department of Mathematics and Statistics [Canada]

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


Volume: Vol. 10 no. 3
Section: Graph and Algorithms
Published on: January 1, 2008
Imported on: March 26, 2015
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 505 times.
This article's PDF has been downloaded 1451 times.