Publisher DOI: 10.37236/4859
Title: Keeping Avoider’s graph almost acyclic
Language: English
Authors: Clemens, Dennis  
Ehrenmüller, Julia 
Person, Yury 
Tran, Tuan 
Keywords: Avoider-Enforcer; Planarity game; Positional games; Threshold bias
Issue Date: 6-Mar-2015
Publisher: EMIS ELibEMS
Source: Electronic Journal of Combinatorics 22 (1): P1.60, 1-12 (2015-03-06)
Abstract (english): 
We consider biased (1:b) Avoider-Enforcer games in the monotone and strict versions. In particular, we show that Avoider can keep his graph being a forest for every but maybe the last round of the game if b ²00nlnn. By this we obtain essentially optimal upper bounds on the threshold biases for the non-planarity game, the non-k-colorability game, and the K-minor game thus addressing a question and improving the results of Hefetz, Krivelevich, Stojakovic, and Szabo. Moreover, we give a slight improvement for the lower bound in the non-planarity game.
URI: http://hdl.handle.net/11420/10042
ISSN: 1077-8926
Journal: The electronic journal of combinatorics 
Institute: Mathematik E-10 
Document Type: Article
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

28
Last Week
0
Last month
1
checked on Jul 6, 2022

SCOPUSTM   
Citations

3
Last Week
0
Last month
0
checked on Jun 29, 2022

Google ScholarTM

Check

Add Files to Item

Note about this record

Cite this record

Export

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