Keeping Avoider's Graph Almost Acyclic

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 b≥200nlnn. By this we obtain essentially optimal upper bounds on the threshold biases for the non- planarity game, the non-k-colorability game, and the Kt-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.