| 伏红勇,谢德政.关于图的星色数的一点注记[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)． |
|
| 摘要点击次数: 2662 |
| 全文下载次数: 2644 |
| 中文摘要: |
| 无向图$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阅读器 |
