The game chromatic number and the game colouring number of classes of oriented cactuses

被引：3

作者：

Andres, Stephan Dominique ^{[1
]}

Hochstaettler, Winfried ^{[1
]}

机构：

[1] FernUni Hagen, Dept Math & Comp Sci, D-58084 Hagen, Germany

来源：

INFORMATION PROCESSING LETTERS | 2011年 / 111卷 / 05期

关键词：

Combinatorial problems; Graph algorithms; Game chromatic number; Game colouring number; Digraph colouring game; PLANAR GRAPHS;

D O I：

10.1016/j.ipl.2010.11.020

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We prove that the game chromatic and the game colouring number of the class of orientations of cactuses with girth of 2 or 3 is 4. We improve this bound for the class of orientations of certain forest-like cactuses to the value of 3. These results generalise theorems on the game colouring number of undirected forests (Faigle et al., 1993 [3]) resp. orientations of forests (Andres, 2009 [1]). For certain undirected cactuses with girth 4 we also obtain the tight bound 4, thus improving a result of Sidorowicz (2007) [8]. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：222 / 226

页数：5

共 11 条

[1] Lightness of digraphs in surfaces and directed game chromatic number [J].

Andres, Stephan Dominique .

DISCRETE MATHEMATICS, 2009, 309 (11) :3564-3579

[2]

Bodlaender H. L., 1991, International Journal of Foundations of Computer Science, V2, P133, DOI 10.1142/S0129054191000091

[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] Edge-partitions of planar graphs and their game coloring numbers [J].

He, WJ ;

Hou, XL ;

Lih, KW ;

Shao, JT ;

Wang, WF ;

Zhu, XD .

JOURNAL OF GRAPH THEORY, 2002, 41 (04) :307-317

[7] A simple competitive graph coloring algorithm [J].

Kierstead, HA .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2000, 78 (01) :57-68

[8]

Nesetril J., 2001, Electron. J. Combin., V8, pR14

[9] The game chromatic number and the game colouring number of cactuses [J].

Sidorowicz, Elzbieta .

INFORMATION PROCESSING LETTERS, 2007, 102 (04) :147-151

[10] The game coloring number of planar graphs [J].

Zhu, XD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1999, 75 (02) :245-258

← 1 2 →