The biased odd cycle game

Abstract

In this paper we consider biased Maker-Breaker games played on the edge set of a given graph $G$. We prove that for every $\hat{I}´>0$ and large enough $n$, there exists a constant $k$ for which if $\hat{I}´(G)\ge \hat{I}´n$ and $\ddot{I}‡(G)\ge k$, then Maker can build an odd cycle in the $(1:b)$ game for $b=O(\frac{n}{{\log }^{2}n})$. 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 $\ddot{I}‡(G)\ge 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$?

10 pages