2010/11/09 by Heidi Gebauer, Gebauer, Heidi
Computer Science · Mathematics · #Artificial Intelligence in Games #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2 #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1011.2178
openalex publication_date 2010/11/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study Maker/Breaker games on the edges of sparse graphs. Maker and Breaker take turns in claiming previously unclaimed edges of a given graph H. Maker aims to occupy a given target graph G and Breaker tries to prevent Maker from achieving his goal. We define a function f and show that for every d-regular graph G on n vertices there is a graph H with at most f(d)n edges such that Maker can occupy a copy of G in the game on H.