| A Note on Star Chromatic Number of Graphs |
| Received:October 25, 2008 Revised:May 16, 2009 |
| Key Words:
star coloring star chromatic number proper coloring.
|
| Fund Project:Supported by the Natural Science Foundation of Chongqing Science and Technology Commission (Grant No.2007BB2123). |
|
| Hits: 2663 |
| Download times: 2645 |
| Abstract: |
| 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. |
| Citation: |
| DOI:10.3770/j.issn:1000-341X.2010.05.009 |
| View Full Text View/Add Comment |
|
|
|
