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

Elżbieta Sidorowicz

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 3, page 499-533
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Elżbieta Sidorowicz. "Colouring game and generalized colouring game on graphs with cut-vertices." Discussiones Mathematicae Graph Theory 30.3 (2010): 499-533. <http://eudml.org/doc/270790>.

@article{ElżbietaSidorowicz2010,
abstract = {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 𝓗 ₖ.},
author = {Elżbieta Sidorowicz},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {colouring game; generalized colouring game},
language = {eng},
number = {3},
pages = {499-533},
title = {Colouring game and generalized colouring game on graphs with cut-vertices},
url = {http://eudml.org/doc/270790},
volume = {30},
year = {2010},
}

TY - JOUR
AU - Elżbieta Sidorowicz
TI - Colouring game and generalized colouring game on graphs with cut-vertices
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 3
SP - 499
EP - 533
AB - 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 𝓗 ₖ.
LA - eng
KW - colouring game; generalized colouring game
UR - http://eudml.org/doc/270790
ER -

References

top
  1. [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. Zbl1091.05023
  2. [2] H.L. Bodlaender, On the complexity of some colouring games, Internat. J. Found. Comput. Sci. 2 (1991) 133-148, doi: 10.1142/S0129054191000091. Zbl0753.05061
  3. [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. [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. Zbl1118.05030
  5. [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 Zbl0966.05028
  6. [6] G. Chartrand and L. Leśniak, Graphs and Digraphs (Fourth Edition Chapman & Hall/CRC, 2005). Zbl1057.05001
  7. [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. Zbl1012.05067
  8. [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. Zbl0928.05022
  9. [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. Zbl1042.05038
  10. [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. Zbl1066.91015
  11. [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. Zbl0796.90082
  12. [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 Zbl0929.05032
  13. [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. Zbl1042.05042
  14. [14] H.A. Kierstead, A simple competitive graph colouring algorithm, J. Combin. Theory (B) 78 (2000) 57-68, doi: 10.1006/jctb.1999.1927. Zbl1024.05029
  15. [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. [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. Zbl1185.91058
  17. [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. Zbl1142.05032
  18. [18] J. Wu and X. Zhu, Relaxed game chromatic number of outerplanar graphs, Ars Combin. 81 (2006) 359-367. Zbl1174.05378
  19. [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. Zbl1136.05022
  20. [20] X. Zhu, The Game Colouring Number of Planar Graphs, J. Combin. Theory (B) 75 (1999) 245-258, doi: 10.1006/jctb.1998.1878. Zbl0933.05052
  21. [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. [22] X. Zhu, Refined activation strategy for the marking game, J. Combin. Theory (B) 98 (2008) 1-18 Zbl1127.05047

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.