On-line Ramsey theory (Q1883676)

Summary: 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 \({\mathcal G}\). The main problem is to recognize the winner for a given pair \(H,{\mathcal 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.