2020/01/18 by Adrian Beker, Beker, Adrian
Computer Science · Mathematics · #05C57 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05C57
paper · pdf · doi:10.48550/arxiv.2001.06735
6 pages
arxiv created 2020/01/18 · openalex publication_date 2020/01/18 · arxiv updated 2020/01/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let n, k be positive integers. The (k+1)-star avoidance game on Kn is played as follows. Two players take it in turn to claim a (previously unclaimed) edge of the complete graph on n vertices. The first player to claim all edges of a subgraph isomorphic to a (k+1)-star loses. Equivalently, each player must keep all degrees in the subgraph formed by his edges at most k. If all edges have been chosen and neither player has lost, the game is declared a draw. We prove that, for each fixed k, the game is a win for the second player for all n sufficiently large.