The game chromatic number and the game colouring number of cactuses

被引：17
作者：
Sidorowicz, Elzbieta [1 ]
机构：
[1] Univ Zielona Gora, Fac Math Comp Sci & Econometr, PL-65516 Zielona Gora, Poland
来源：
INFORMATION PROCESSING LETTERS | 2007年 / 102卷 / 04期
关键词：
combinatorial problems; competitive algorithms; game colouring number; game chromatic number;
D O I：
10.1016/j.ipl.2006.12.003
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We consider the colouring game and the marking game. A graph G is a cactus if any two cycles of G have at most one common vertex. We prove that chi(g) (C) = col(g) (C) = 5 for family of cactuses C. (c) 2006 Elsevier B.V. All rights reserved.
引用
收藏
页码：147 / 151
页数：5
相关论文
共 13 条
[1]  
Bodlaender H. L., 1991, International Journal of Foundations of Computer Science, V2, P133, DOI 10.1142/S0129054191000091
[2]  
Chartrand G., 2016, GRAPHS DIGRAPHS
[3]  
FAIGLE U, 1993, ARS COMBINATORIA, V35, P143
[4]  
Guan DJ, 1999, J GRAPH THEOR, V30, P67, DOI 10.1002/(SICI)1097-0118(199901)30:1<67::AID-JGT7>3.0.CO
[5]  
2-M
[6]  
Jensen T, 1995, Graph Colouring Problems
[7]  
Kierstead, 2001, ELECTRON J COMB, V8, pR12
[8]   Marking games and the oriented game chromatic number of partial k-trees [J].
Kierstead, HA ;
Tuza, Z .
GRAPHS AND COMBINATORICS, 2003, 19 (01) :121-129
[9]  
LICHTENSTAIN D, 1980, J ACM, V37, P393
[10]  
Nesetril J., 2001, ELECTRON J COMB, V8, pR14, DOI [10.37236/1613, DOI 10.37236/1613]
12