2023/03/07 by Xiumin Wang, Huang Zhong, Wang, Xiumin +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Artificial Intelligence in Games #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2303.04152
openalex publication_date 2023/03/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1982, Harary introduced the concept of Ramsey achievement game on graphs. Given a graph F with no isolated vertices. Consider the following game played on the complete graph Kn by two players Alice and Bob. First, Alice colors one of the edges of Kn blue, then Bob colors a different edge red, and so on. The first player who can complete the formation of F in his color is the winner. The minimum n for which Alice has a winning strategy is the achievement number of F, denoted by a(F). If we replace Kn in the game by the completed bipartite graph Kn,n, we get the bipartite achievement number, denoted by ba(F). In his seminal paper, Harary proposed an open problem of determining bipartite achievement numbers for trees. In this paper, we correct ba(mK2)=m+1 to m and disprove ba(K1,m)=2m-2 from Erickson and Harary, and extend their results on bipartite achievement numbers. We also find the exact values of achievement numbers for matchings, and the exact values or upper and lower bounds of bipartite achievement numbers on matchings, stars, and double stars. Our upper bounds are obtained by deriving efficient winning strategies for Alice.