Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. The game of arborici ...
Conference paper

The game of arboricity

Tomasz Bartnicki ORCID (1), Jaroslaw Grytczuk ORCID (1), Hal Kierstead (2)
(1) Faculty of Mathematics, Computer Science and Econometric [Zielona Góra]
(2) Department of Mathematics and Statistics [Tempe, Arizona]
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Proceedings
DOI
10.46298/dmtcs.3428
License
https://about.hal.science/hal-authorisation-v1
Indicators
539
Views
602
Downloads

The game of arboricity

Tomasz Bartnicki ORCID (1), Jaroslaw Grytczuk ORCID (1), Hal Kierstead (2)
(1) Faculty of Mathematics, Computer Science and Econometric [Zielona Góra]
(2) Department of Mathematics and Statistics [Tempe, Arizona]
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
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • arboricity
  • two-player strategies
  • activation strategy
Cited by

Source: OpenCitations

  • The coloring game on matroids

    Discrete Mathematics

    Authors : Michał Lasoń ORCID

    Journal reference : Volume 340, 2016, pp. 796-799

    DOI : 10.1016/j.disc.2016.11.020

  • On monotonicity in Maker–Breaker graph colouring games

    Discrete Applied Mathematics

    Authors : Lawrence Hollom ORCID

    Journal reference : Volume 347, 2024, pp. 131-138

    DOI : 10.1016/j.dam.2024.01.007

  • On Game Chromatic Vertex-Critical Graphs

    Bulletin of the Malaysian Mathematical Sciences Society

    Authors : Marko Jakovac ORCID, Daša Štesl

    Journal reference : Volume 46, 2022, pp.

    DOI : 10.1007/s40840-022-01418-6

  • On Monotonicity in Maker-Breaker Graph Colouring Games

    SSRN Electronic Journal

    Authors : Lawrence Hollom

    Journal reference : Volume , 2023, pp.

    DOI : 10.2139/ssrn.4538929

  • Coloring Graphs Using Two Colors While Avoiding Monochromatic Cycles

    Open Repository and Bibliography (University of Liège)

    Authors : Fabrice Talla Nobibon, Cor A. J. Hurkens ORCID, Roel Leus ORCID, Frits C. R. Spieksma ORCID

    Journal reference : Volume 24, 2011, pp. 485-499

    DOI : 10.1287/ijoc.1110.0466

  • Indicated coloring of matroids

    Discrete Applied Mathematics

    Authors : Michał Lasoń ORCID

    Journal reference : Volume 179, 2014, pp. 241-243

    DOI : 10.1016/j.dam.2014.07.004

  • Coloring Graphs While Avoiding Monochromatic Cycles

    SSRN Electronic Journal

    Authors : Fabrice Talla Nobibon, Cor Hurkens ORCID, Roel Leus ORCID, Frits Spieksma ORCID

    Journal reference : Volume , 2010, pp.

    DOI : 10.2139/ssrn.1683889

  • Majority coloring game

    Homo Politicus (Academy of Humanities and Economics in Lodz)

    Authors : Bartłomiej Bosek ORCID, Jarosław Grytczuk ORCID, Gabriel Jakóbczak

    Journal reference : Volume 255, 2018, pp. 15-20

    DOI : 10.1016/j.dam.2018.07.020

  • An Annotated Bibliography on the Thickness, Outerthickness, and Arboricity of a Graph

    Missouri Journal of Mathematical Sciences

    Authors : Erkki Mäkinen ORCID, Timo Poranen ORCID

    Journal reference : Volume 24, 2012, pp.

    DOI : 10.35834/mjms/1337950501

  • Domination Game and an Imagination Strategy

    SIAM Journal on Discrete Mathematics

    Authors : Boštjan Brešar ORCID, Sandi Klavžar ORCID, Douglas F. Rall ORCID

    Journal reference : Volume 24, 2010, pp. 979-991

    DOI : 10.1137/100786800

  • Indicated coloring game on Cartesian products of graphs

    Discrete Applied Mathematics

    Authors : Boštjan Brešar ORCID, Marko Jakovac ORCID, Daša Štesl

    Journal reference : Volume 289, 2020, pp. 320-326

    DOI : 10.1016/j.dam.2020.11.007
Preview
Loading PDF preview...