PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 1 | 31-42
Tytuł artykułu

Note On The Game Colouring Number Of Powers Of Graphs

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
36
Numer
1
Strony
31-42
Opis fizyczny
Daty
wydano
2016-02-01
otrzymano
2014-06-04
poprawiono
2015-03-26
zaakceptowano
2015-03-26
online
2016-01-19
Twórcy
  • 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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1841
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.