Density of the circular chromatic numbers of series-parallel graphs

被引:8
作者
Pan, ZS [1 ]
Zhu, XD [1 ]
机构
[1] Natl Sun Yat Sen Univ, Dept Appl Math, Kaohsiung 80424, Taiwan
关键词
circular chromatic number; series-parallel graph; labeling method;
D O I
10.1002/jgt.10171
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Suppose G is a series-parallel graph. It was proved in [3] that either chi(c)(G) = 3 or chi(c)(G) less than or equal to 8/3. So none of the rationals in the interval (8/3, 3) is the circular chromatic number of a series-parallel graph. This paper proves that for every rational r epsilon [2, 8/3] boolean OR {3} there exists a series-parallel graph G with chi(c)(G) = r. (C) 2004 Wiley Periodicals, Inc.
引用
收藏
页码:57 / 68
页数:12
相关论文
共 17 条
[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]  
Hell P, 2000, J GRAPH THEOR, V33, P14, DOI 10.1002/(SICI)1097-0118(200001)33:1<14::AID-JGT2>3.0.CO
[5]  
2-#
[6]   Construction of Kn-minor free graphs with given circular chromatic number [J].
Liaw, SC ;
Pan, ZS ;
Zhu, XD .
DISCRETE MATHEMATICS, 2003, 263 (1-3) :191-206
[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]  
Niven I., 1991, INTRO THEORY NUMBERS
[10]  
Oxley J., 1993, MATROID THEORY