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 xs（G）, is the smallest integer k for...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 xs（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 A, then xs（G） ≤ [7△3/2]], which gets better bound than those of Fertin, Raspaud and Reed.展开更多
The notion of the star chromatic number of a graph is a generalization of the chromatic number. In this paper. we calculate the star chromatic numbers of three infinite families of planar graphs. The first two familie...The notion of the star chromatic number of a graph is a generalization of the chromatic number. In this paper. we calculate the star chromatic numbers of three infinite families of planar graphs. The first two families are derived from a 3-or 5-wheel by subdivisions. their star chromatic numbers being 2+2/(2n + 1). 2+3/(3n + 1)and 2+3/ (3n - 1), respectively. The third family of planar graphs are derived from n odd wheels by Hajos construction with star chromatic numbers 3 + 1/n. which is a generalization of one resnlt of Gao et al.展开更多
The concept of the star chromatic number of a graph was introduced by A.Vince in ,which is a natural generalizition of the chromatic number of a graph.In this paper,we investigate the star chromatic number of a famil...The concept of the star chromatic number of a graph was introduced by A.Vince in ,which is a natural generalizition of the chromatic number of a graph.In this paper,we investigate the star chromatic number of a family of planar graphs.More precisely, a family of planar graphs whose star chromatic numbers are between 2 and 3 are disscused,which answers the open problem posed by Vince in .展开更多
基金Supported by the Natural Science Foundation of Chongqing Science and Technology Commission (Grant No.2007BB2123)
文摘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 xs（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 A, then xs（G） ≤ [7△3/2]], which gets better bound than those of Fertin, Raspaud and Reed.
文摘The notion of the star chromatic number of a graph is a generalization of the chromatic number. In this paper. we calculate the star chromatic numbers of three infinite families of planar graphs. The first two families are derived from a 3-or 5-wheel by subdivisions. their star chromatic numbers being 2+2/(2n + 1). 2+3/(3n + 1)and 2+3/ (3n - 1), respectively. The third family of planar graphs are derived from n odd wheels by Hajos construction with star chromatic numbers 3 + 1/n. which is a generalization of one resnlt of Gao et al.
文摘The concept of the star chromatic number of a graph was introduced by A.Vince in ,which is a natural generalizition of the chromatic number of a graph.In this paper,we investigate the star chromatic number of a family of planar graphs.More precisely, a family of planar graphs whose star chromatic numbers are between 2 and 3 are disscused,which answers the open problem posed by Vince in .
