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

Sidorowicz, Elżbieta

Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 3, pp. 499-533.

Résumé

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 ₖ.

Détail

Keywords: colouring game, generalized colouring game

Bibliographie

[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:3144::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:167::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