Online Ramsey theory for a triangle on F-free graphs

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 48
  • Download : 0
Given a class C of graphs and a fixed graph H, the online Ramsey game for H on 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, 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, Haluszczak, and Kierstead [Electron. J. Combin. 11 (2004), p. 60].
Publisher
WILEY
Issue Date
2019-10
Language
English
Article Type
Article
Citation

JOURNAL OF GRAPH THEORY, v.92, no.2, pp.152 - 171

ISSN
0364-9024
DOI
10.1002/jgt.22445
URI
http://hdl.handle.net/10203/269819
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0