PDF
Discussiones Mathematicae Graph Theory 30(3) (2010)
499-533
DOI: https://doi.org/10.7151/dmgt.1510
COLOURING GAME AND GENERALIZED COLOURING GAME ON GRAPHS WITH CUT-VERTICES
Elżbieta Sidorowicz
Faculty of Mathematics, Computer Science and Econometrics
University of Zielona Góra
Z. Szafrana 4a, 65-516 Zielona Góra, Poland
e-mail: e.sidorowicz@wmie.uz.zgora.pl
Abstract
For k ≥ 2 we define a class of graphs Hk = {G: every block of G has at most k vertices}. The class Hk 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 Hk.Keywords: colouring game, generalized colouring game.
2010 Mathematics Subject Classification: 05C15, 05C57.
References
[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. |
Received 27 May 2010
Revised 28 June 2010
Accepted 28 June 2010
Close