TY - JOUR
T1 - The biased odd cycle game
AU - Ferber, Asaf
AU - Glebov, Roman
AU - Krivelevich, Michael
AU - Liu, Hong
AU - Palmer, Cory
AU - Valla, Tomáš
AU - Vizer, Máté
PY - 2013/4/17
Y1 - 2013/4/17
N2 - In this paper we consider biased Maker-Breaker games played on the edge set of a given graph G. We prove that for every δ > 0 and large enough n, there exists a constant k for which if δ(G) ≥ δ (and) χ(G) ≥ k, then Maker can build an odd cycle in the (1: b) game for b = O(n/log2n). We also consider the analogous game log2 n 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 χ(G) ≥ 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?.
AB - In this paper we consider biased Maker-Breaker games played on the edge set of a given graph G. We prove that for every δ > 0 and large enough n, there exists a constant k for which if δ(G) ≥ δ (and) χ(G) ≥ k, then Maker can build an odd cycle in the (1: b) game for b = O(n/log2n). We also consider the analogous game log2 n 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 χ(G) ≥ 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?.
KW - DLR conjecture
KW - Maker-Breaker games
KW - Odd cycle game
UR - http://www.scopus.com/inward/record.url?scp=84876445336&partnerID=8YFLogxK
U2 - 10.37236/2819
DO - 10.37236/2819
M3 - Article
AN - SCOPUS:84876445336
SN - 1077-8926
VL - 20
JO - Electronic Journal of Combinatorics
JF - Electronic Journal of Combinatorics
IS - 2
ER -