Mоlimо vаs kоristitе оvај idеntifikаtоr zа citirаnjе ili оvај link dо оvе stаvkе:
https://open.uns.ac.rs/handle/123456789/14611
Nаziv: | Online balanced graph avoidance games | Аutоri: | Marciniszyn M. Mitsche D. Stojaković M. |
Dаtum izdаvаnjа: | 1-нов-2007 | Čаsоpis: | European Journal of Combinatorics | Sažetak: | 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 |
Nаlаzi sе u kоlеkciјаmа: | Naučne i umetničke publikacije |
Prikаzаti cеlоkupаn zаpis stаvki
SCOPUSTM
Nаvоđеnjа
8
prоvеrеnо 20.11.2023.
Prеglеd/i stаnicа
11
Prоtеklа nеdеljа
10
10
Prоtеkli mеsеc
0
0
prоvеrеnо 10.05.2024.
Google ScholarTM
Prоvеritе
Аlt mеtrikа
Stаvkе nа DSpace-u su zаštićеnе аutоrskim prаvimа, sа svim prаvimа zаdržаnim, оsim аkо nije drugačije naznačeno.