Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184385
Contributor : Coordination Episciences Iam <>
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

Identifiers

  • HAL Id : hal-01184385, version 1

Collections

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. ⟨hal-01184385⟩

Share

Metrics

Record views

368

Files downloads

677