2022/04/17 by Stojaković, Miloš, Stratijev, Jelena
#05C57 #91A24 #91A46 #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #G.2.2
paper · doi:10.48550/arxiv.2204.07971
Given an increasing graph property \cal F, the strong Avoider-Avoider \cal F game is played on the edge set of a complete graph. Two players, Red and Blue, take turns in claiming previously unclaimed edges with Red going first, and the player whose graph possesses \cal F first loses the game. If the property \cal F is "containing a fixed graph H", we refer to the game as the H game. We prove that Blue has a winning strategy in two strong Avoider-Avoider games, P4 game and \cal CC>3 game, where \cal CC>3 is the property of having at least one connected component on more than three vertices. We also study a variant, the strong CAvoider-CAvoider games, with additional requirement that the graph of each of the players must stay connected throughout the game. We prove that Blue has a winning strategy in the strong CAvoider-CAvoider games S3 and P4, as well as in the Cycle game, where the players aim at avoiding all cycles.