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 -