Geodesic
The game of arboricity
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2005_special_250_a37,
     author = {Bartnicki, Tomasz and Grytczuk, Jaroslaw and Kierstead, Hal},
     title = {The game of arboricity},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
     year = {2005},
     doi = {10.46298/dmtcs.3428},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3428/}
}
TY  - JOUR
AU  - Bartnicki, Tomasz
AU  - Grytczuk, Jaroslaw
AU  - Kierstead, Hal
TI  - The game of arboricity
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3428/
DO  - 10.46298/dmtcs.3428
LA  - en
ID  - DMTCS_2005_special_250_a37
ER  - 
%0 Journal Article
%A Bartnicki, Tomasz
%A Grytczuk, Jaroslaw
%A Kierstead, Hal
%T The game of arboricity
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3428/
%R 10.46298/dmtcs.3428
%G en
%F DMTCS_2005_special_250_a37
Bartnicki, Tomasz; Grytczuk, Jaroslaw; Kierstead, Hal. The game of arboricity. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005). doi : 10.46298/dmtcs.3428. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3428/

Cité par Sources :