On-line Ramsey theory

J. A. Grytczuk, M. Hałuszczak, Henry Kierstead

Research output: Contribution to journalArticlepeer-review

24 Scopus citations


The Ramsey game we consider in this paper is played on an unbounded set of vertices by two players, called Builder and Painter. In one move Builder introduces a new edge and Painter paints it red or blue. The goal of Builder is to force Painter to create a monochromatic copy of a fixed target graph H, keeping the constructed graph in a prescribed class G. The main problem is to recognize the winner for a given pair H, G. In particular, we prove that Builder has a winning strategy for any k-colorable graph H in the game played on k-colorable graphs. Another class of graphs with this strange self-unavoidability property is the class of forests. We show that the class of outerplanar graphs does not have this property. The question of whether planar graphs are self-unavoidable is left open. We also consider a multicolor version of Ramsey on-line game. To extend our main result for 3-colorable graphs we introduce another Ramsey type game, which seems interesting in its own right.

Original languageEnglish (US)
Pages (from-to)1-10
Number of pages10
JournalElectronic Journal of Combinatorics
Issue number1 R
StatePublished - Sep 9 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'On-line Ramsey theory'. Together they form a unique fingerprint.

Cite this