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.
@article{bwmeta1.element.doi-10_7151_dmgt_1841,
author = {Stephan Dominique Andres and Andrea Theuser},
title = {Note On The Game Colouring Number Of Powers Of Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {31-42},
zbl = {1329.05100},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1841}
}
Stephan Dominique Andres; Andrea Theuser. Note On The Game Colouring Number Of Powers Of Graphs. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 31-42. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1841/
[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[Crossref] | Zbl 1029.05047
[2] T. Bartnicki, J. Grytczuk, H.A. Kierstead and X. Zhu, The map-coloring game, Amer. Math. Monthly 114 (2007) 793–803. | Zbl 1247.05074
[3] H.L. Bodlaender, On the complexity of some coloring games, Internat. J. Found. Comput. Sci. 2 (1991) 133–147. | Zbl 0753.05061
[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[Crossref]
[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[Crossref]
[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[WoS][Crossref]
[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. | Zbl 0796.90082
[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[Crossref]
[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[Crossref] | Zbl 0809.05044
[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[WoS][Crossref]
[13] D. Yang, Coloring games on squares of graphs, Discrete Math. 312 (2012) 1400–1406. doi:10.1016/j.disc.2012.01.004[Crossref][WoS]
[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[Crossref]
[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[Crossref] | Zbl 0947.05031
[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[Crossref] | Zbl 1127.05047