1 |
The game Grundy arboricity of graphsLiu, Jin-yu 31 August 2012 (has links)
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.
|
Page generated in 0.103 seconds