On-line Ramsey numbers for paths and stars - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2008

On-line Ramsey numbers for paths and stars

Résumé

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
Fichier principal
Vignette du fichier
632-3473-2-PB.pdf (109.2 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00972333 , version 1 (03-04-2014)

Identifiants

Citer

J. A. Grytczuk, H. A. Kierstead, P. Prałat. On-line Ramsey numbers for paths and stars. Discrete Mathematics and Theoretical Computer Science, 2008, Vol. 10 no. 3 (3), pp.63--74. ⟨10.46298/dmtcs.427⟩. ⟨hal-00972333⟩

Collections

TDS-MACS
91 Consultations
1223 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More