图的星边色数的一个新的上界

A New Upper Bound on Star Chromatic Number of Graphs

图的着色问题是图论中的一个重要问题,图论领域的诸多学者研究了图的各种着色.运用Lovsz局部引理,研究了图的星边着色(图G的星边着色是G的一个正常的边着色,并且使得G中无长为4的路是2-边着色的;图G的星边色数是G的所有星边着色中所使用的最小颜色数,记为χ'se(G)),并证明了最大度为Δ(Δ≥2)的简单无向图G的星边色数新的上界为χ'se(G)≤「9(Δ-1)3/2?.

The coloring of graphs is an important issue in the graph theory. Many scholars in the field of graph theory studied variant kinds of coloring of graphs. In this paper, the Lovtisz Local Lemma is used to research the star edge-coloring of graphs （ A star edge-coloring of a undirected graph G is a proper edge-coloring of G such that any path of length four in G is not bicolored. The star Chromatic number of a undirected graph G, denoted by χ＇se （G）, is the smallest integer k for which G admits a star edge-coloring with k colors）. It is proved that a new upper bound of star chromatic number is χ＇se（G）≤「9（Δ-1）3/2]. for any graph G with maximum degree Δ（Δ≥2）.