On-line Ramsey theory

J. A. Grytczuk ; M. Hałuszczak ; H. A. Kierstead

The electronic journal of combinatorics, Tome 11 (2004) no. 1

Résumé

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 ${\cal G}$. The main problem is to recognize the winner for a given pair $H,{\cal 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.

Détail

DOI : 10.37236/1810

Classification : 05C55, 05C38, 15A15, 05A15, 15A18, 05D10, 05C15, 91A43
Mots-clés : Ramsey game, \(k\)-colorable graph, Ramsey on-line game