Fast winning strategies in avoider-enforcer games

DOI10.1007/S00373-009-0870-8zbMATH Open1181.91044arXiv0806.0280OpenAlexW2013432272MaRDI QIDQ844236FDOQ844236

Authors: Dan Hefetz, Michael Krivelevich, Miloš Stojaković, Tibor Szabó 

Publication date: 18 January 2010

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: In numerous positional games the identity of the winner is easily determined. In this case one of the more interesting questions is not {em who} wins but rather {em how fast} can one win. These type of problems were studied earlier for Maker-Breaker games; here we initiate their study for unbiased Avoider-Enforcer games played on the edge set of the complete graph $K_n$ on $n$ vertices. For several games that are known to be an Enforcer's win, we estimate quite precisely the minimum number of moves Enforcer has to play in order to win. We consider the non-planarity game, the connectivity game and the non-bipartite game.

Full work available at URL: https://arxiv.org/abs/0806.0280

Recommendations

• On winning fast in Avoider-Enforcer games
• Fast winning strategies in positional games
• Avoider-enforcer star games
• On avoider-enforcer games
• Avoider-enforcer star games

zbMATH Keywords

bipartiteconnectivityplanarity

Mathematics Subject Classification ID

Hypergraphs (05C65) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24) Combinatorial games (91A46)

Cites Work

• Avoider-Enforcer games
• Planarity, Colorability, and Minor Games
• Combinatorial Games
• Fast winning strategies in maker-breaker games
• On Biased Positional Games
• On positional games
• A Winning Strategy for the Ramsey Graph Game
• A universal planar graph under the minor relation
• How long can a graph be kept planar?

Cited In (10)

• On winning fast in Avoider-Enforcer games
• How long can a graph be kept planar?
• Sharp thresholds for half-random games. II
• Avoider-enforcer: the rules of the game
• Fast winning strategies in positional games
• Game matching number of graphs
• Planarity, Colorability, and Minor Games
• On avoider-enforcer games
• Transitive avoidance games
• Blockers for triangulations of a convex polygon and a geometric maker-breaker game

This page was built for publication: Fast winning strategies in avoider-enforcer games

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