Graph Saturation Games

We study [Lee, J. D., Riet, A. F-Saturation Games, submitted to Discrete Mathematics, arXiv:1406.1500 [math.CO]; Lee, J. D., Riet, A. New F-Saturation Games on Directed Graphs, submitted to Discrete Mathematics, arXiv:1409.0565 [math.CO]] F-saturation games, first introduced by Füredi, Reimer and Seress [Füredi, Z., Reimer, D. and Seress, A., Hajnal's Triangle-Free Game and Extremal Graph Problems, Congr. Numer. 82 (1991), 123–128] in 1991, and named as such by West [West, D., The F-Saturation Game (2009) and Game Saturation Number (2011), http://www.math.uiuc.edu/~west/regs/fsatgame.html (last visited March 6, 2015)]. The main question is to determine the length of the game whilst avoiding various classes of graphs, playing on a large complete graph. We show lower bounds on the length of path-avoiding games, and more precise results for short paths. We show sharp results for the tree avoiding game and the star avoiding game. We also study directed analogues of these games. We show tight results on the walk-avoiding game. We also examine an intermediate game played on undirected graphs, such that there exists an orientation avoiding a given family of directed graphs, and show bounds on the score. This last game is known to be equivalent to a recent game studied in [Hefetz, D., Krivelevich, M., Naor, A., Stojaković, M., On Saturation Games, preprint, arXiv:1406.2111v2 [math.CO]], and we give new bounds for biased versions of this game.