Tomasz Bartnicki ; Jaroslaw Grytczuk ; Hal Kierstead

The game of arboricity
dmtcs:3428 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

https://doi.org/10.46298/dmtcs.3428
The game of arboricity
Authors: Tomasz Bartnicki ^{1}; Jaroslaw Grytczuk ^{1}; Hal Kierstead ^{2}
NULL##NULL##NULL
Tomasz Bartnicki;Jaroslaw Grytczuk;Hal Kierstead
1 Faculty of Mathematics, Computer Science and Econometric [Zielona Góra]
2 Department of Mathematics and Statistics [Tempe, Arizona]
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 $\textit{game arboricity}$ of $G$, denoted by $A_g(G)$. We prove that $A_g(G) \leq 3k$ for any graph $G$ of arboricity $k$, and that there are graphs such that $A_g(G) \geq 2k2$. The upper bound is achieved by a suitable version of the activation strategy, used earlier for the vertex coloring game. We also provide other strategie based on induction.