Cyclic chromatic number of 3-connected plane graphs

被引:22
作者
Enomoto, H
Hornák, M
Jendrol, S
机构
[1] Keio Univ, Dept Math, Kohoku Ku, Yokohama, Kanagawa 2238522, Japan
[2] Safarik Univ, Dept Geometry & Algebra, Kosice 04154, Slovakia
关键词
cyclic coloring; cyclic chromatic number;
D O I
10.1137/S0895480198346150
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let G be a 3-connected plane graph. Plummer and Toft [J. Graph Theory, 11 (1987), pp. 507-515] conjectured that chi (c)(G) less than or equal to Delta*(G) + 2, where chi (c)(G) is the cyclic chromatic number of G and Delta*(G) the maximum face size of G. Hornak and Jendrol' [J. Graph Theory, 30 (1999), pp. 177-189] and Borodin and Woodall [SIAM J. Discrete Math., submitted] independently proved this conjecture when ( G) is large enough. Moreover, Borodin and Woodall proved a stronger statement that chi (c)(G) less than or equal to Delta*(G) + 1 holds if Delta*(G) greater than or equal to 122. In this paper, we prove that chi (c)(G) less than or equal to Delta*(G) + 1 holds if Delta*(G) greater than or equal to 60.
引用
收藏
页码:121 / 137
页数:17
相关论文
共 7 条
[1]   CONTRACTILE EDGES IN 3-CONNECTED GRAPHS [J].
ANDO, K ;
ENOMOTO, H ;
SAITO, A .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1987, 42 (01) :87-93
[2]  
BORODIN OV, UNPUB SIAM J DISCRET
[3]   MINIMAL N-TUPLE CONNECTED GRAPHS [J].
HALIN, R .
MATHEMATISCHE ANNALEN, 1969, 182 (03) :175-&
[4]  
Hornák M, 1999, J GRAPH THEOR, V30, P177
[5]  
Jensen T. R., 1995, Graph Coloring Problems
[6]  
Ore O., 1969, Recent Progress in Combinatorics, P287
[7]   CYCLIC COLORATION OF 3-POLYTOPES [J].
PLUMMER, MD ;
TOFT, B .
JOURNAL OF GRAPH THEORY, 1987, 11 (04) :507-515