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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.