The game chromatic index of forests of maximum degree Δ ≥ 5

被引：23
作者：
Andres, SD [1 ]
机构：
[1] Univ Cologne, Math Inst, D-50931 Cologne, Germany
来源：
DISCRETE APPLIED MATHEMATICS | 2006年 / 154卷 / 09期
关键词：
game chromatic index; forest; graph colouring games; game chromatic number; strongly unmatched edge;
D O I：
10.1016/j.dam.2005.05.031
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Using a refinement of the methods of Erdbs et al. [Note on the game chromatic index of trees, Theoret. Comput. Sci. 313 (2004) 371-376] we prove that the game chromatic index of forests of maximum node degree 5 is at most 6. This improves the previously known upper bound 7 for this parameter. The bound 6 is tight [P. Erdos, U. Faigle, W. Hochstattler, W. Kern, Note on the game chromatic index of trees, Theoret. Comput. Sci. 313 (2004) 371-376]. (c) 2006 Elsevier B.V. All rights reserved.
引用
收藏
页码：1317 / 1323
页数：7
相关论文
共 10 条
[1]  
Andres SD, 2003, THESIS U KOLN, P49
[2]  
Bodlaender H. L., 1991, International Journal of Foundations of Computer Science, V2, P133, DOI 10.1142/S0129054191000091
[3]  
Cai LZ, 2001, J GRAPH THEOR, V36, P144, DOI 10.1002/1097-0118(200103)36:3<144::AID-JGT1002>3.0.CO
[4]  
2-F
[5]   Relaxed game chromatic number of graphs [J].
Chou, CY ;
Wang, WF ;
Zhu, XD .
DISCRETE MATHEMATICS, 2003, 262 (1-3) :89-98
[6]   A bound for the game chromatic number of graphs [J].
Dinski, T ;
Zhu, XD .
DISCRETE MATHEMATICS, 1999, 196 (1-3) :109-115
[7]   Note on the game chromatic index of trees [J].
Erdös, PL ;
Faigle, U ;
Hochstättler, W ;
Kern, W .
THEORETICAL COMPUTER SCIENCE, 2004, 313 (03) :371-376
[8]  
FAIGLE U, 1993, ARS COMBINATORIA, V35, P143
[9]  
HE W, 1999, GAME CHROMATIC INDEX, V3
[10]   A simple competitive graph coloring algorithm [J].
Kierstead, HA .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2000, 78 (01) :57-68
1