Geodesic
The biased odd cycle game
The electronic journal of combinatorics, Tome 20 (2013) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

In this paper we consider biased Maker-Breaker games played on the edge set of a given graph $G$. We prove that for every $\delta>0$ and large enough $n$, there exists a constant $k$ for which if $\delta(G)\geq \delta n$ and $\chi(G)\geq k$, then Maker can build an odd cycle in the $(1:b)$ game for $b=O\left(\frac{n}{\log^2 n}\right)$. We also consider the analogous game where Maker and Breaker claim vertices instead of edges. This is a special case of the following well known and notoriously difficult problem due to Duffus, Łuczak and Rödl: is it true that for any positive constants $t$ and $b$, there exists an integer $k$ such that for every graph $G$, if $\chi(G)\geq k$, then Maker can build a graph which is not $t$-colorable, in the $(1:b)$ Maker-Breaker game played on the vertices of $G$?
DOI : 10.37236/2819
Classification : 05C57, 91A43
Mots-clés : positional games

Asaf Ferber  1   ; Roman Glebov    ; Michael Krivelevich    ; Hong Liu    ; Cory Palmer    ; Tomas Valla    ; Máté Vizer 

1 Tel-Aviv University 
@article{10_37236_2819,
     author = {Asaf Ferber and Roman Glebov and Michael Krivelevich and Hong Liu and Cory Palmer and Tomas Valla and M\'at\'e Vizer},
     title = {The biased odd cycle game},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {2},
     doi = {10.37236/2819},
     zbl = {1267.05170},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2819/}
}
TY  - JOUR
AU  - Asaf Ferber
AU  - Roman Glebov
AU  - Michael Krivelevich
AU  - Hong Liu
AU  - Cory Palmer
AU  - Tomas Valla
AU  - Máté Vizer
TI  - The biased odd cycle game
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2819/
DO  - 10.37236/2819
ID  - 10_37236_2819
ER  - 
%0 Journal Article
%A Asaf Ferber
%A Roman Glebov
%A Michael Krivelevich
%A Hong Liu
%A Cory Palmer
%A Tomas Valla
%A Máté Vizer
%T The biased odd cycle game
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2819/
%R 10.37236/2819
%F 10_37236_2819
Asaf Ferber; Roman Glebov; Michael Krivelevich; Hong Liu; Cory Palmer; Tomas Valla; Máté Vizer. The biased odd cycle game. The electronic journal of combinatorics, Tome 20 (2013) no. 2. doi: 10.37236/2819

Cité par Sources :