伏红勇,谢德政.关于图的星色数的一点注记[J].数学研究及应用,2010,30(5):841~844
关于图的星色数的一点注记
A Note on Star Chromatic Number of Graphs
投稿时间:2008-10-25  最后修改时间:2009-05-16
DOI:10.3770/j.issn:1000-341X.2010.05.009
中文关键词:  星着色  星色数  正常着色.
英文关键词:star coloring  star chromatic number  proper coloring.
基金项目:重庆市科委自然科学基金计划资助项目(Grant No.2007BB2123).
作者单位
伏红勇 重庆大学数学与统计学院, 重庆 401331; 重庆大学经济与工商管理学院, 重庆 400044 
谢德政 重庆大学数学与统计学院, 重庆 401331 
摘要点击次数: 1541
全文下载次数: 1583
中文摘要:
      无向图$G$的星着色是指图$G$的正常的顶点着色并且使得长为3的路不着双色.无向图$G$的星色数,记为$\chi_{s}(G)$,是指图$G$所有用$k$种颜色的星着色中所使用的最小的正整数$k$. 本文证明了若$G$是最大度为$\Delta$的图,则$\chi_{s}(G)\leq\lceil7\Delta^{\frac{3}{2}}\rceil$, 从而推广了文献[1]的主要结果.
英文摘要:
      A star coloring of an undirected graph $G$ is a proper coloring of $G$ such that no path of length $3$ in $G$ is bicolored. The star chromatic number of an undirected graph $G$, denoted by $\chi_{s}(G)$, is the smallest integer $k$ for which $G$ admits a star coloring with $k$ colors. In this paper, we show that if $G$ is a graph with maximum degree $\Delta$, then $\chi_{s}(G)\leq\lceil7\Delta^{\frac{3}{2}}\rceil$, which gets better bound than those of Fertin, Raspaud and Reed.
查看全文  查看/发表评论  下载PDF阅读器