Keeping avoider's graph almost acyclic

MaRDI QIDQ2260635zbMATH OpenFDO

Authors Yanyan Li

Publication date 11 March 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.1482, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p60

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Avoider-Enforcer gamesbiased gamesplanarity gamepositional gamesthreshold bias

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Games on graphs (graph-theoretic aspects) (05C57) 2-person games (91A05) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Abstract: 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 $bgeq200nlnn$. 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_t$-minor game thus addressing a question and improving the results of Hefetz, Krivelevich, Stojakovi'c, and Szab'o. Moreover, we give a slight improvement for the lower bound in the non-planarity game.

Recommendations

• Avoider-enforcer star games
• Avoider-enforcer: the rules of the game
• Avoider-Enforcer: the rules of the game
• Avoider-forcer games on hypergraphs with small rank
• On winning fast in Avoider-Enforcer games

Cites work

• A Hamiltonian game on \(K_{n,n}\)
• A matching game
• A Solution of the Shannon Switching Game
• Avoider-Enforcer games
• Avoider-enforcer: the rules of the game
• Biased Positional Games
• Biased positional games for which random strategies are nearly optimal
• Combinatorial Games
• Hamiltonian games
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• Planarity, Colorability, and Minor Games
• Ramsey games
• Remarks on positional games. I

Cited in

(12)

• How long can a graph be kept planar?
• On the odd cycle game and connected rules
• Avoidable paths in graphs
• On the separation conjecture in avoider-enforcer games
• Avoider-Enforcer games
• Waiter-Client and Client-Waiter planarity, colorability and minor games
• Avoider-Enforcer: the rules of the game
• Avoider-forcer games on hypergraphs with small rank
• Avoider-enforcer star games
• Avoidance couplings on non‐complete graphs
• The Avoider-Enforcer game in hypergraphs of rank 3
• Avoider-enforcer: the rules of the game

This page was built for publication: Keeping avoider's graph almost acyclic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2260635)