# The game of arboricity

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 $\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 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 other strategie based on induction.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [8 references]

https://hal.inria.fr/hal-01184385
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 11:38:55 AM
Last modification on : Thursday, May 11, 2017 - 1:02:51 AM
Long-term archiving on: : Sunday, November 15, 2015 - 11:05:18 AM

### File

dmAE0113.pdf
Publisher files allowed on an open archive

### Citation

Tomasz Bartnicki, Jaroslaw Grytczuk, Hal Kierstead. The game of arboricity. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.63-66, ⟨10.46298/dmtcs.3428⟩. ⟨hal-01184385⟩

Record views