Geodesic
Note On The Game Colouring Number Of Powers Of Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 31-42.

Voir la notice de l'article provenant de la source Library of Science

We generalize the methods of Esperet and Zhu [6] providing an upper bound for the game colouring number of squares of graphs to obtain upper bounds for the game colouring number of m-th powers of graphs, m ≥ 3, which rely on the maximum degree and the game colouring number of the underlying graph. Furthermore, we improve these bounds in case the underlying graph is a forest.
Keywords: game colouring number, marking game, graph power, game chromatic number, forest 
@article{DMGT_2016_36_1_a2,
     author = {Andres, Stephan Dominique and Theuser, Andrea},
     title = {Note {On} {The} {Game} {Colouring} {Number} {Of} {Powers} {Of} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {31--42},
     publisher = {mathdoc},
     volume = {36},
     number = {1},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a2/}
}
TY  - JOUR
AU  - Andres, Stephan Dominique
AU  - Theuser, Andrea
TI  - Note On The Game Colouring Number Of Powers Of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 31
EP  - 42
VL  - 36
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a2/
LA  - en
ID  - DMGT_2016_36_1_a2
ER  - 
%0 Journal Article
%A Andres, Stephan Dominique
%A Theuser, Andrea
%T Note On The Game Colouring Number Of Powers Of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 31-42
%V 36
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a2/
%G en
%F DMGT_2016_36_1_a2
Andres, Stephan Dominique; Theuser, Andrea. Note On The Game Colouring Number Of Powers Of Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 31-42. http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a2/

[1] G. Agnarsson and M.M. Halldórsson, Coloring powers of planar graphs, SIAM J. Discrete Math. 16 (2003) 651–662. doi:10.1137/S0895480100367950

[2] T. Bartnicki, J. Grytczuk, H.A. Kierstead and X. Zhu, The map-coloring game, Amer. Math. Monthly 114 (2007) 793–803.

[3] H.L. Bodlaender, On the complexity of some coloring games, Internat. J. Found. Comput. Sci. 2 (1991) 133–147.

[4] T. Dinski and X. Zhu, A bound for the game chromatic number of graphs, Discrete Math. 196 (1999) 109–115. doi:10.1016/S0012-365X(98)00197-6

[5] P. Erdős and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966) 61–99. doi:10.1007/BF02020444

[6] L. Esperet and X. Zhu, Game colouring of the square of graphs, Discrete Math. 309 (2009) 4514–4521. doi:10.1016/j.disc.2009.02.014

[7] U. Faigle, U. Kern, H. Kierstead and W.T. Trotter, On the game chromatic number of some classes of graphs, Ars Combin. 35 (1993) 143–150.

[8] M. Gardner, Mathematical games, Scientific American 244(4) (1981) 18–26.

[9] H.A. Kierstead, A simple competitive graph coloring algorithm, J. Combin. Theory Ser. B 78 (2000) 57–68. doi:10.1006/jctb.1999.1927

[10] H.A. Kierstead and W.T. Trotter, Planar graph coloring with an uncooperative partner, J. Graph Theory 18 (1994) 569–584. doi:10.1002/jgt.3190180605

[11] A. Theuser, Die spielchromatische Zahl der Potenz eines Graphen, Diploma Thesis (FernUniversität in Hagen, 2014), in German.

[12] J. Wu and X. Zhu, Lower bounds for the game colouring number of partial k-trees and planar graphs, Discrete Math. 308 (2008) 2637–2642. doi:10.1016/j.disc.2007.05.023

[13] D. Yang, Coloring games on squares of graphs, Discrete Math. 312 (2012) 1400–1406. doi:10.1016/j.disc.2012.01.004

[14] X. Zhu, The game coloring number of planar graphs, J. Combin. Theory Ser. B 75 (1999) 245–258. doi:10.1006/jctb.1998.1878

[15] X. Zhu, The game coloring number of pseudo partial k-trees, Discrete Math. 215 (2000) 245–262. doi:10.1016/S0012-365X(99)00237-X

[16] X. Zhu, Refined activation strategy for the marking game, J. Combin. Theory Ser. B 98 (2008) 1–18. doi:10.1016/j.jctb.2007.04.004