On-line Ramsey numbers for paths and stars

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
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (3), pp.63--74
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00972333
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 3 avril 2014 - 16:13:32
Dernière modification le : mercredi 29 novembre 2017 - 10:26:20
Document(s) archivé(s) le : jeudi 3 juillet 2014 - 16:40:24

Fichier

632-3473-2-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00972333, version 1

Collections

Citation

J. A. Grytczuk, H. A. Kierstead, P. Prałat. On-line Ramsey numbers for paths and stars. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (3), pp.63--74. 〈hal-00972333〉

Partager

Métriques

Consultations de la notice

58

Téléchargements de fichiers

948