The circular chromatic number of series-parallel graphs of large odd girth

被引：17

作者：

Pan, ZS ^{[1
]}

Zhu, XD ^{[1
]}

机构：

[1] Natl Sun Yat Sen Univ, Dept Appl Math, Kaohsiung 80424, Taiwan

来源：

DISCRETE MATHEMATICS | 2002年 / 245卷 / 1-3期

关键词：

circular chromatic number; circular flow number; series-parallel graph; odd girth;

D O I：

10.1016/S0012-365X(01)00144-3

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Suppose G is a series-parallel graph, We prove that if G has odd girth at least 6k - 1 then chi(c)(G) less than or equal to 8k/(4k - 1); if G has odd girth at least 6k + 1 then chi(c)(G) less than or equal to (4k + 1)/2k; if G has odd girth at least 6k + 3 then chi(c)(G) less than or equal to (4k + 3)/(2k + 1). (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：235 / 246

页数：12

共 29 条

[1] A NOTE ON THE STAR CHROMATIC NUMBER [J].

BONDY, JA ;

HELL, P .

JOURNAL OF GRAPH THEORY, 1990, 14 (04) :479-482

[2]

Chien CY, 2000, J GRAPH THEOR, V33, P185, DOI 10.1002/(SICI)1097-0118(200004)33:4<185::AID-JGT1>3.0.CO

[3]

2-N

[4]

GALLUCCIO A, IN PRESS J COMBIN B

[5]

Goddyn LA, 1998, J GRAPH THEOR, V28, P155, DOI 10.1002/(SICI)1097-0118(199807)28:3<155::AID-JGT5>3.0.CO

[6]

2-J

[7]

Hell P, 2000, J GRAPH THEOR, V33, P14, DOI 10.1002/(SICI)1097-0118(200001)33:1<14::AID-JGT2>3.0.CO

[8]

2-#

[9]

Klostermeyer W, 2000, J GRAPH THEOR, V33, P109, DOI 10.1002/(SICI)1097-0118(200002)33:2<109::AID-JGT5>3.0.CO

[10]

2-F

← 1 2 3 →