BROWSE

Related Scientist

Researcher

엄상일
수리 및 계산 과학 연구단
more info

Online Ramsey theory for a triangle on F‐free graphs

Cited 0 time in webofscience Cited 0 time in scopus
15 Viewed 2 Downloaded
Title
Online Ramsey theory for a triangle on F‐free graphs
Author(s)
Hojin Choi; Ilkyoo Choi; Jisu Jeong; Sang‐il Oum
Publication Date
2019-10
Journal
JOURNAL OF GRAPH THEORY, v.92, no.2, pp.152 - 171
Publisher
WILEY-BLACKWELL
Abstract
Given a class 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 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 forC3 on the class of K4‐minor‐free graphs, extending a result by Grytczuk, Hałuszczak, and Kierstead [Electron. J. Combin. 11 (2004), p. 60]. © 2019 Wiley Periodicals, Inc.
URI
https://pr.ibs.re.kr/handle/8788114/6851
ISSN
1097-0118
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > Journal Papers (저널논문)
Files in This Item:
Online Ramsey theory for a triangle on F-free graphs.pdfDownload

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse