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 arboricityArticle

Authors: Tomasz Bartnicki ORCID1; Jaroslaw Grytczuk 1; Hal Kierstead 2

  • 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 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.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: arboricity,two-player strategies,activation strategy,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

9 Documents citing this article

Consultation statistics

This page has been seen 185 times.
This article's PDF has been downloaded 345 times.