Note on the game chromatic index of trees

被引：17

作者：

Erdös, PL

Faigle, U

Hochstättler, W

Kern, W

机构：

[1] A Renyi Inst Math, H-1053 Budapest, Hungary

[2] Univ Cologne, Zentrum Angew Informat Koln, D-50931 Cologne, Germany

[3] BTU Cottbus, Dept Math, D-03013 Cottbus, Germany

[4] Univ Twente, Dept Appl Math, NL-7500 AE Enschede, Netherlands

来源：

THEORETICAL COMPUTER SCIENCE | 2004年 / 313卷 / 03期

关键词：

game theory; chromatic index;

D O I：

10.1016/j.tcs.2002.10.002

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study edge coloring games defining the so-called game chromatic index of a graph. It has been reported that the game chromatic index of trees with maximum degree Delta = 3 is at most Delta + 1. We show that the same holds true in case Delta greater than or equal to 6, which would leave only the cases Delta =4 and 5 open. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：371 / 376

页数：6

共 9 条

[1] Berge C, 1985, GRAPHS
[2] BODLAENDER HL, 1990, SPRINGER LECT NOTES
[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] A new game chromatic number
Chen, G
Schelp, RH
Shreve, WE
[J]. EUROPEAN JOURNAL OF COMBINATORICS, 1997, 18 (01) : 1 - 9
[6] FAIGLE U, 1993, ARS COMBINATORIA, V35, P143
[7] PLANAR GRAPH-COLORING WITH AN UNCOOPERATIVE PARTNER
KIERSTEAD, HA
TROTTER, WT
[J]. JOURNAL OF GRAPH THEORY, 1994, 18 (06) : 569 - 584
[8] Vizing V., 1964, DISKRET ANAL, V3, P9
[9] Vizing V. G., 1965, KIBERNETIKA KIEV, V1965, P29

← 1 →