2023/12/31 by József Balogh, Balogh, József, Ce Chen +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2401.00386
openalex publication_date 2023/12/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the Constructor-Blocker game, two players, Constructor and Blocker, alternatively claim unclaimed edges of the complete graph Kn. For given graphs F and H, Constructor can only claim edges that leave her graph F-free, while Blocker has no restrictions. Constructor's goal is to build as many copies of H as she can, while Blocker attempts to stop this. The game ends once there are no more edges that Constructor can claim. The score g(n,H,F) of the game is the number of copies of H in Constructor's graph at the end of the game, when both players play optimally and Constructor plays first. In this paper, we extend results of Patkós, Stojaković and Vizer on g(n, H, F) to many pairs of H and F: We determine g(n, H, F) when H=Kr and χ(F)>r, also when both H and F are odd cycles, using Szemerédi's Regularity Lemma. We also obtain bounds of g(n, H, F) when H=K3 and F=K2,2.