Note On The Game Colouring Number Of Powers Of Graphs

• Autorzy: Stephan Dominique Andres , Andrea Theuser
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

game colouring number; marking game; graph power; game chromatic number; forest

Kategorie tematyczne

• 91A43: Games involving graphs
• 05C05: Trees
• 05C15: Coloring of graphs and hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 1
• Strony: 31-42

Daty

wydano

2016-02-01

otrzymano

2014-06-04

poprawiono

2015-03-26

zaakceptowano

2015-03-26

online

2016-01-19

Twórcy

autor

Stephan Dominique Andres

• FernUniversität in Hagen, Fakultät für Mathematik und Informatik, IZ, Universitätsstr. 1, 58084 Hagen, Germany

autor

Andrea Theuser

• FernUniversität in Hagen, Fakultät für Mathematik und Informatik, IZ, Universitätsstr. 1, 58084 Hagen, Germany

Bibliografia

• [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]
• [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[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.
• [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]
• [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]
• [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]

Identyfikatory

DOI

10.7151/dmgt.1841