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 [J].

Chen, G ;

Schelp, RH ;

Shreve, WE .

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 [J].

KIERSTEAD, HA ;

TROTTER, WT .

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 →