International Symposium on Mathematical Science at Niigata University 2016
The Game Grundy Arboricity of Graphs
*Jin-Yu Liu (National Sun Yat-Sen University (NSYSU))
Given a graph $G = (V, E)$, two players, Alice and Bob, alternate their turns to choose uncolored edges to be colored. Whenever an uncolored edge is chosen, it is colored by the least positive integer so that no monochromatic cycle is created. Alice's goal is to minimize the total number of colors used in the game, while Bob's goal is to maximize it. The game Grundy arboricity of $G$ is the number of colors used in the game when both players use optimal strategies. This thesis discusses the game Grundy arboricity of graphs. It is proved that if a graph $G$ has arboricity $k$, then the game Grundy arboricity of $G$ is at most $3k-1$. If a graph $G$ has an acyclic orientation $D$ with maximum out-degree at most $k$, then the game Grundy arboricity of $G$ is at most $3k-2$.