Star-Edge Coloring Of Some Special Classes Of Graphs

The coloring of the graphs, one of the more interesting and rapidly growing areas of researches in graph theory, has great theoretical value and applied background. In 2004, Fertin et al[1] introduce the concept of star coloring of graphs. In 2006, Liu xin-sheng et al[2] introduce the concept of star-edge coloring of graphs, a star-edge coloring of graph G is a proper edge coloring of G such that any path of length 4 in G is not bicolored. The star-edge chromatic index of G, denoted byχ'_s(G), is the smallest integer k for which G admits a star-edge coloring with k colors. Not only are there the important significance for star coloring of graphs, but also the close relation to the acyclic edge colorings(Gr(?)nbaum ,1973,[47]) and the strong edge colorings(Erd(?)s, 1986, [44]). A great number of problems about the star-edge coloring theory are unsolved so far. In this thesis, we study the star-edge coloring of some special classes of graphs, and obtain the following result.1. We study the star-edge coloring of Cartesian product graphs of some special classes of graphs, obtain the chromatic index ofP_m口P_n,P_m口C_n,P_m口S_n,P_m口F_n,P_m口W_n.2. The star-edge coloring of the Generalized Petersen Graph and the result ofχ'_s{P(n,2)).3. The star-edge coloring chromatic index on join-graph.