In the Avoider-Enforcer game on the complete graph Kn, the players (Avoider and Enforcer) each take an edge in turn. Given a graph property P, Enforcer wins the game if Avoider's graph has the property P. An important parameter is τE(P), the smallest integer t such that Enforcer can win the game against any opponent in t rounds. In this paper, let ℱ be an arbitrary family of graphs and P be the property that a member of ℱ is a subgraph or is an induced subgraph. We determine the asymptotic value of τE(P) when ℱ contains no bipartite graph and establish that τE(P) = o(n2)if ℱ contains a bipartite graph. The proof uses the game of JumbleG and the Szemeredi regularity lemma.
|Original language||English (US)|
|Number of pages||8|
|Journal||SIAM Journal on Discrete Mathematics|
|State||Published - 2009|
- Positional games
- Regularity lemma
ASJC Scopus subject areas