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 𝓗 ₖ.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1510,
author = {El\.zbieta Sidorowicz},
title = {Colouring game and generalized colouring game on graphs with cut-vertices},
journal = {Discussiones Mathematicae Graph Theory},
volume = {30},
year = {2010},
pages = {499-533},
zbl = {1217.05095},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1510}
}
Elżbieta Sidorowicz. Colouring game and generalized colouring game on graphs with cut-vertices. Discussiones Mathematicae Graph Theory, Tome 30 (2010) pp. 499-533. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1510/
[000] [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. | Zbl 1091.05023
[001] [2] H.L. Bodlaender, On the complexity of some colouring games, Internat. J. Found. Comput. Sci. 2 (1991) 133-148, doi: 10.1142/S0129054191000091. | Zbl 0753.05061
[002] [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.
[003] [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. | Zbl 1118.05030
[004] [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 | Zbl 0966.05028
[005] [6] G. Chartrand and L. Leśniak, Graphs and Digraphs (Fourth Edition Chapman & Hall/CRC, 2005). | Zbl 1057.05001
[006] [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. | Zbl 1012.05067
[007] [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. | Zbl 0928.05022
[008] [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. | Zbl 1042.05038
[009] [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. | Zbl 1066.91015
[010] [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. | Zbl 0796.90082
[011] [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 | Zbl 0929.05032
[012] [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. | Zbl 1042.05042
[013] [14] H.A. Kierstead, A simple competitive graph colouring algorithm, J. Combin. Theory (B) 78 (2000) 57-68, doi: 10.1006/jctb.1999.1927. | Zbl 1024.05029
[014] [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.
[015] [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. | Zbl 1185.91058
[016] [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. | Zbl 1142.05032
[017] [18] J. Wu and X. Zhu, Relaxed game chromatic number of outerplanar graphs, Ars Combin. 81 (2006) 359-367. | Zbl 1174.05378
[018] [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. | Zbl 1136.05022
[019] [20] X. Zhu, The Game Colouring Number of Planar Graphs, J. Combin. Theory (B) 75 (1999) 245-258, doi: 10.1006/jctb.1998.1878. | Zbl 0933.05052
[020] [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.
[021] [22] X. Zhu, Refined activation strategy for the marking game, J. Combin. Theory (B) 98 (2008) 1-18 | Zbl 1127.05047