关于图的星色数的一点注记

A Note on Star Chromatic Number of Graphs

中文关键词:  星着色  星色数  正常着色.

英文关键词:star coloring  star chromatic number  proper coloring.

中文摘要:

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