A New Upper Bound on Star Chromatic Number of Graphs

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 Lovsz 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).