Online Ramsey theory for a triangle on $F$-free graphs
Preprint
Abstract
Given a class $\mathcal{C}$ of graphs and a fixed graph $H$, the online Ramsey game for $H$ on $\mathcal C$ is a game between two players Builder and Painter as follows: an unbounded set of vertices is given as an initial state, and on each turn Builder introduces a new edge with the constraint that the resulting graph must be in $\mathcal C$, and Painter colors the new edge either red or blue. Builder wins the game if Painter is forced to make a monochromatic copy of $H$ at some point in the game. Otherwise, Painter can avoid creating a monochromatic copy of $H$ forever, and we say Painter wins the game. We initiate the study of characterizing the graphs $F$ such that for a given graph $H$, Painter wins the online Ramsey game for $H$ on $F$-free graphs. We characterize all graphs $F$ such that Painter wins the online Ramsey game for $C_3$ on the class of $F$-free graphs, except when $F$ is one particular graph. We also show that Painter wins the online Ramsey game for $C_3$ on the class of $K_4$-minor-free graphs, extending a result by Grytczuk, Ha{\l}uszczak, and Kierstead.
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- The on-line degree Ramsey number of cyclesDiscrete Mathematics, 2013
- Online Ramsey games for triangles in random graphsDiscrete Mathematics, 2010
- On-line Ramsey NumbersSIAM Journal on Discrete Mathematics, 2010
- Online Ramsey Games in Random GraphsCombinatorics, Probability and Computing, 2009
- Upper Bounds for Online Ramsey Games in Random GraphsCombinatorics, Probability and Computing, 2009
- Balanced Online Ramsey Games in Random GraphsThe Electronic Journal of Combinatorics, 2009
- On a Problem of Formal Logic2009
- Coloring number and on-line Ramsey theory for graphs and hypergraphsCombinatorica, 2009
- Online balanced graph avoidance gamesEuropean Journal of Combinatorics, 2007
- Ramsey Games Against a One-Armed BanditCombinatorics, Probability and Computing, 2003