Note On The Game Colouring Number Of Powers Of Graphs

Stephan Dominique Andres; Andrea Theuser

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 1, page 31-42
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Stephan Dominique Andres, and Andrea Theuser. "Note On The Game Colouring Number Of Powers Of Graphs." Discussiones Mathematicae Graph Theory 36.1 (2016): 31-42. <http://eudml.org/doc/276975>.

@article{StephanDominiqueAndres2016,
abstract = {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.},
author = {Stephan Dominique Andres, Andrea Theuser},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {game colouring number; marking game; graph power; game chromatic number; forest},
language = {eng},
number = {1},
pages = {31-42},
title = {Note On The Game Colouring Number Of Powers Of Graphs},
url = {http://eudml.org/doc/276975},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Stephan Dominique Andres
AU - Andrea Theuser
TI - Note On The Game Colouring Number Of Powers Of Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 1
SP - 31
EP - 42
AB - 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.
LA - eng
KW - game colouring number; marking game; graph power; game chromatic number; forest
UR - http://eudml.org/doc/276975
ER -

References

top
  1. [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] Zbl1029.05047
  2. [2] T. Bartnicki, J. Grytczuk, H.A. Kierstead and X. Zhu, The map-coloring game, Amer. Math. Monthly 114 (2007) 793–803. Zbl1247.05074
  3. [3] H.L. Bodlaender, On the complexity of some coloring games, Internat. J. Found. Comput. Sci. 2 (1991) 133–147. Zbl0753.05061
  4. [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. [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. [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. [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. Zbl0796.90082
  8. [8] M. Gardner, Mathematical games, Scientific American 244(4) (1981) 18–26. 
  9. [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. [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] Zbl0809.05044
  11. [11] A. Theuser, Die spielchromatische Zahl der Potenz eines Graphen, Diploma Thesis (FernUniversität in Hagen, 2014), in German. 
  12. [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. [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. [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. [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] Zbl0947.05031
  16. [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] Zbl1127.05047

NotesEmbed ?

top

You must be logged in to post comments.