PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2010 | 30 | 3 | 499-533
Tytuł artykułu

Colouring game and generalized colouring game on graphs with cut-vertices

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
For k ≥ 2 we define a class of graphs 𝓗 ₖ = {G: every block of G has at most k vertices}. The class 𝓗 ₖ contains among other graphs forests, Husimi trees, line graphs of forests, cactus graphs. We consider the colouring game and the generalized colouring game on graphs from 𝓗 ₖ.
Słowa kluczowe
Wydawca
Rocznik
Tom
30
Numer
3
Strony
499-533
Opis fizyczny
Daty
wydano
2010
otrzymano
2010-05-27
poprawiono
2010-06-28
zaakceptowano
2010-06-28
Twórcy
  • Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, Z. Szafrana 4a, 65-516 Zielona Góra, Poland
Bibliografia
  • [1] S.D. Andres, The game chromatic index of forests of maximum degree Δ ≥ 5, Discrete Applied Math. 154 (2006) 1317-1323, doi: 10.1016/j.dam.2005.05.031.
  • [2] H.L. Bodlaender, On the complexity of some colouring games, Internat. J. Found. Comput. Sci. 2 (1991) 133-148, doi: 10.1142/S0129054191000091.
  • [3] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed(s), Advances in Graph Theory Vishwa International Publication Gulbarga, 1991) 41-68.
  • [4] M. Borowiecki and E. Sidorowicz, Generalized game colouring of graphs, Discrete Math. 307 (2007) 1225-1231, doi: 10.1016/j.disc.2005.11.060.
  • [5] L. Cai and X. Zhu, Game chromatic index of k-degenerate graphs, J. Graph Theory 36 (2001) 144-155, doi: 10.1002/1097-0118(200103)36:3<144::AID-JGT1002>3.0.CO;2-F
  • [6] G. Chartrand and L. Leśniak, Graphs and Digraphs (Fourth Edition Chapman & Hall/CRC, 2005).
  • [7] Ch. Chou, W. Wang and X. Zhu, Relaxed game chromatic number of graphs, Discrete Math. 262 (2003) 89-98, doi: 10.1016/S0012-365X(02)00521-6.
  • [8] 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.
  • [9] C. Dunn and H.A. Kierstead, The relaxed game chromatic number of outerplanar graphs, J. Graph Theory 46 (2004) 69-106, doi: 10.1002/jgt.10172.
  • [10] P.L. Erdös, U. Faigle, W. Hochstättler and W. Kern, Note on the game chromatic index of trees, Theoretical Computer Science 313 (2004) 371-376, doi: 10.1016/j.tcs.2002.10.002.
  • [11] U. Faigle, U. Kern, H.A. Kierstead and W.T. Trotter, On the game chromatic number of some classes of graphs, Ars Combin. 35 (1993) 143-150.
  • [12] D. Guan and X. Zhu, The game chromatic number of outerplanar graphs, J. Graph Theory 30 (1999) 67-70, doi: 10.1002/(SICI)1097-0118(199901)30:1<67::AID-JGT7>3.0.CO;2-M
  • [13] W. He, J. Wu and X. Zhu, Relaxed game chromatic number of trees and outerplanar graphs, Discrete Math. 281 (2004) 209-219, doi: 10.1016/j.disc.2003.08.006.
  • [14] H.A. Kierstead, A simple competitive graph colouring algorithm, J. Combin. Theory (B) 78 (2000) 57-68, doi: 10.1006/jctb.1999.1927.
  • [15] H.A. Kierstead and Zs. Tuza, Marking games and the oriented game chromatic number of partial k-trees, Graphs Combin. 19 (2003) 121-129, doi: 10.1007/s00373-002-0489-5.
  • [16] E. Sidorowicz, The game chromatic number and the game colouring number of cactuses, Information Processing Letters 102 (2007) 147-151, doi: 10.1016/j.ipl.2006.12.003.
  • [17] J. Wu and X. Zhu, Lower bounds for the game colouring number of planar graphs and partial k-trees, Discrete Math. 308 (2008) 2637-2642, doi: 10.1016/j.disc.2007.05.023.
  • [18] J. Wu and X. Zhu, Relaxed game chromatic number of outerplanar graphs, Ars Combin. 81 (2006) 359-367.
  • [19] D. Yang and H.A. Kierstead, Asymmetric marking games on line graphs, Discrete Math. 308 (2008) 1751-1755, doi: 10.1016/j.disc.2007.03.082.
  • [20] X. Zhu, The Game Colouring Number of Planar Graphs, J. Combin. Theory (B) 75 (1999) 245-258, doi: 10.1006/jctb.1998.1878.
  • [21] X. Zhu, Game colouring number of pseudo partial k-trees, Discrete Math. 215 (2000) 245-262, doi: 10.1016/S0012-365X(99)00237-X.
  • [22] X. Zhu, Refined activation strategy for the marking game, J. Combin. Theory (B) 98 (2008) 1-18
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1510
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ć.