The biased odd cycle game (Q1953485): Difference between revisions

Summary: 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 \textit{D. Duffus} et al. [Stud. Sci. Math. Hung. 34, No. 1--3, 141--149 (1998; Zbl 0928.91011)]: 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\)?