Keeping Avoider's Graph Almost Acyclic

  • Dennis Clemens
  • Julia Ehrenmüller
  • Yury Person
  • Tuan Tran
Keywords: Positional games, Avoider-Enforcer, planarity game, threshold bias


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 \geq 200 n \ln n$. 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ć, and Szabó. Moreover, we give a slight improvement for the lower bound in the non-planarity game.

Article Number