Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650597 | Discrete Mathematics | 2008 | 6 Pages |
Abstract
Using a fixed set of colors C, Ann and Ben color the edges of a graph G so that no monochromatic cycle may appear. Ann wins if all edges of G have been colored, while Ben wins if completing a coloring is not possible. The minimum size of C for which Ann has a winning strategy is called the game arboricity of G , denoted by Ag(G)Ag(G). We prove that Ag(G)⩽3kAg(G)⩽3k for any graph G of arboricity k , and that there are graphs such that Ag(G)⩾2k-2Ag(G)⩾2k-2. The upper bound is achieved by a suitable version of the activation strategy, used earlier for the vertex coloring game. We also provide two other strategies based on induction and acyclic colorings.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
T. Bartnicki, J.A. Grytczuk, H.A. Kierstead,