Online Ramsey theory for a triangle on F‐free graphs.
In: Journal of Graph Theory, Jg. 92 (2019-10-01), Heft 2, S. 152-171
Online
academicJournal
Zugriff:
Given a class C of graphs and a fixed graph H, the online Ramsey game for H onC 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 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 C3 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 C3 on the class of K4‐minor‐free graphs, extending a result by Grytczuk, Hałuszczak, and Kierstead [Electron. J. Combin. 11 (2004), p. 60]. [ABSTRACT FROM AUTHOR]
Copyright of Journal of Graph Theory is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Titel: |
Online Ramsey theory for a triangle on F‐free graphs.
|
---|---|
Autor/in / Beteiligte Person: | Choi, Hojin ; Choi, Ilkyoo ; Jeong, Jisu ; Oum, Sang‐il |
Link: | |
Zeitschrift: | Journal of Graph Theory, Jg. 92 (2019-10-01), Heft 2, S. 152-171 |
Veröffentlichung: | 2019 |
Medientyp: | academicJournal |
ISSN: | 0364-9024 (print) |
DOI: | 10.1002/jgt.22445 |
Schlagwort: |
|
Sonstiges: |
|