Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/14611
Title: | Online balanced graph avoidance games | Authors: | Marciniszyn M. Mitsche D. Stojaković M. |
Issue Date: | 1-Nov-2007 | Journal: | European Journal of Combinatorics | Abstract: | We introduce and study online balanced coloring games on the random graph process. The game is played by a player we call Painter. Edges of the complete graph with n vertices are introduced two at a time, in a random order. For each pair of edges, Painter immediately and irrevocably chooses one of the two possibilities to color one of them red and the other one blue. His goal is to avoid creating a monochromatic copy of a small fixed graph F for as long as possible. We show that the duration of the game is determined by a threshold function mH = mH (n) for certain graph-theoretic structures, e.g., cycles. That is, for every graph H in this family, Painter will asymptotically almost surely (a.a.s.) lose the game after m = ω (mH) edge pairs in the process. On the other hand, there exists an essentially optimal strategy: if the game lasts for m = o (mH) moves, Painter can a.a.s. successfully avoid monochromatic copies of H. Our attempt is to determine the threshold function for several classes of graphs. © 2007 Elsevier Ltd. All rights reserved. | URI: | https://open.uns.ac.rs/handle/123456789/14611 | ISSN: | 01956698 | DOI: | 10.1016/j.ejc.2007.04.004 |
Appears in Collections: | Naučne i umetničke publikacije |
Show full item record
SCOPUSTM
Citations
8
checked on Nov 20, 2023
Page view(s)
11
Last Week
10
10
Last month
0
0
checked on May 10, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.