Construction of Kn-minor free graphs with given circular chromatic number

被引：8

作者：

Liaw, SC ^{[1
]}

Pan, ZS ^{[1
]}

Zhu, XD ^{[1
]}

机构：

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

来源：

DISCRETE MATHEMATICS | 2003年 / 263卷 / 1-3期

关键词：

circular chromatic numbers; K-n-minor free graphs; series-parallel construction; planar graphs; Hadwiger conjecture;

D O I：

10.1016/S0012-365X(02)00529-0

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

For each integer n greater than or equal to 5 and each rational number r in the interval [2, n - I], we construct a K-n-minor free graph G with chi(c)(G) = r. This answers a question asked by Zhu (Discrete Mathematics, 229 (1-3) (2001) 371). In case n = 5, the constructed graphs are actually planar. Such planar graphs were first constructed in J. Graph Theory 24 (1997) 33 (for E [2, 3]) and in J. Combin. Theory 76 (1999) 170 (for r is an element of [3,4]). However, our construction and proof are much simpler. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：191 / 206

页数：16

共 17 条

[1]

BAUSLAUGH B, 1998, B I COMBIN APPL, V24, P79

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

BONDY, JA ;

HELL, P .

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

[3]

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

[4]

2-N

[5]

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

[6]

2-#

[7]

Moser D, 1997, J GRAPH THEOR, V24, P33, DOI 10.1002/(SICI)1097-0118(199701)24:1<33::AID-JGT5>3.0.CO

[8]

2-K

[9]

PAN Z, 1999, UNPUB DENSITY CIRCUL

[10] The circular chromatic number of series-parallel graphs of large odd girth [J].

Pan, ZS ;

Zhu, XD .

DISCRETE MATHEMATICS, 2002, 245 (1-3) :235-246

← 1 2 →