Loading [MathJax]/jax/output/HTML-CSS/jax.js

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 arboricityConference paper

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 game arboricity of G, denoted by Ag(G). We prove that Ag(G)3k for any graph G of arboricity k, and that there are graphs such that Ag(G)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.


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]

10 Documents citing this article

Consultation statistics

This page has been seen 260 times.
This article's PDF has been downloaded 404 times.