A Note on Star Chromatic Number of Graphs

DOI：10.3770/j.issn:1000-341X.2010.05.009

 作者 单位 伏红勇 重庆大学数学与统计学院, 重庆 401331 重庆大学经济与工商管理学院, 重庆 400044 谢德政 重庆大学数学与统计学院, 重庆 401331

无向图$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.