2012/10/16 by Asaf Ferber, Ferber, Asaf, Roman Glebov +13
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1210.4342
10 pages
arxiv created 2013/04/11 · arxiv updated 2013/04/12
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)≥ δn and χ(G)≥ k, then Maker can build an odd cycle in the (1:b) game for b=O((n)/(log2 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 χ(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?