The biased odd cycle game

Asaf Ferber, Roman Glebov, Michael Krivelevich, Hong Liu, Cory Palmer, Tomáš Valla, Máté Vizer

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 δ > 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?.

Original languageEnglish
JournalElectronic Journal of Combinatorics
Volume20
Issue number2
DOIs
StatePublished - Apr 17 2013

Keywords

  • DLR conjecture
  • Maker-Breaker games
  • Odd cycle game

Fingerprint

Dive into the research topics of 'The biased odd cycle game'. Together they form a unique fingerprint.

Cite this