摘要
图的星色数是通常色数概念的推广.本文求出了几类由轮图导出的平面图的星色数.前两类是由3-或5-轮图经细分等构造出的,其星色数分别为2+2/(2n+1),2+3/(3n+1)和2+3/(3n-1).第三类平面图是由n-轮图经过Hajos构造得到的,其星色数为3+1/n.本类图的星色数结果推广了已有结论.
The notion of star chromatic number of a graph is a generalization of the chromatic number. In this paper, we calculate the star chromatic numbers of three infinite families of planar graphs. The first two families are derived from a 3-or 5-wheel by subdivisions, their star chromatic numbers being 2 + 2/(2n + 1), 2 + 3/(3n + 1) and 2 + 3/(3n - 1) separately. The third family of planar graphs are derived from n odd wheels by Hajos construction with star chromatic numbers 3 + 1/n, which is a generalization of the result of Gao et al.
出处
《数学学报(中文版)》
SCIE
CSCD
北大核心
2004年第5期1031-1036,共6页
Acta Mathematica Sinica:Chinese Series
基金
国家自然科学基金资助项目
关键词
(k
d)-着色
星色数
平面图
(k,d)- coloring
Star chromatic number
Planar graph