1Institut für Mathematik, Technische Universität Hamburg-Harburg 2Institut für Mathematik, Goethe-Universität 3Institut für Mathematik, Freie Universität Berlin
The electronic journal of combinatorics, Tome 22 (2015) no. 1
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.
Dennis Clemens
1
;
Julia Ehrenmüller
1
;
Yury Person
2
;
Tuan Tran
3
1
Institut für Mathematik, Technische Universität Hamburg-Harburg
2
Institut für Mathematik, Goethe-Universität
3
Institut für Mathematik, Freie Universität Berlin
@article{10_37236_4859,
author = {Dennis Clemens and Julia Ehrenm\"uller and Yury Person and Tuan Tran},
title = {Keeping avoider's graph almost acyclic},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {1},
doi = {10.37236/4859},
zbl = {1312.91024},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4859/}
}
TY - JOUR
AU - Dennis Clemens
AU - Julia Ehrenmüller
AU - Yury Person
AU - Tuan Tran
TI - Keeping avoider's graph almost acyclic
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/4859/
DO - 10.37236/4859
ID - 10_37236_4859
ER -
%0 Journal Article
%A Dennis Clemens
%A Julia Ehrenmüller
%A Yury Person
%A Tuan Tran
%T Keeping avoider's graph almost acyclic
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/4859/
%R 10.37236/4859
%F 10_37236_4859
Dennis Clemens; Julia Ehrenmüller; Yury Person; Tuan Tran. Keeping avoider's graph almost acyclic. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/4859
