The Star Edge Coloring Of Some Subcubic Graphs

Coloring of graphs is one of the most important branches of graph theory.A star coloring of a graph G is a proper vertex coloring of G such that any path of length 3 in G is not bicolored.The star chromatic number of the graph G,denoted by χst(G),is the minimum number of colors for which G has a star coloring.The star edge coloring was initiated in 2008 by Liu and Deng.A star edge coloring of a graph G is a proper edge coloring with at least three distinct colors used on the edges of every path and cycle of length four.The minimum number of colors for which G admits a star edge coloring is called the star chromatic index,denoted by χst’(G).A strong edge-coloring of a graph G,denoted by χs’(G),is a proper edge coloring so that no edge can be adjacent to two edges with the same color in it every color class giving an induced matching.The definition was introduced by Fouquet and Jolivet(1983)to solve a problem involving radio networks and their frequencies.Since the star chromatic index of a given graph has a certain relationship with its strong chromatic index,the list star chromatic index,and the acyclic edge chromatic number,it is obvious to see that the star edge coloring of a graph G is a strong edge coloring of it,then the star chromatic index of a given graph is no more than its strong edge chromatic index.Thus,the study of the star chromatic index of a graph has a certain significance for the strong chromatic index,the list edge chromatic number,and the acyclic chromatic index.In the thesis,we further study the star edge coloring of subcubic graphs and mainly study the star chromatic index of the generalized Petersen graph and the Sierpinski graphs.Besides,we also give some feasible star edge coloring of these graphs,which insure the conjecture(The star edge chromatic index of subcubic is no more than 6,which is put forwarded by Mohar et al.)is correct.We also construct a family of special cubic graphs and obtain that their star chromatic indexes are 6 based on a cubic graph with the star chromatic index 6.This paper is organised as follows:In Chapter one,we introduce the studying background of star edge coloring,giving the defi-nition and symbols used in the thesis,and sorting out the research results of star edge coloring.In Chapter two,we give the star chromatic index values of generalized Petersen graphs p(n,1),p(n,2),p(n,3).We prove the lower bound of p(n,1),p(n,2),p(n,3)by the relation between the star chromatic index of the given graph and the star chromatic index of its subgraph.To find a feasible lower bounded star edge coloring which can be generalized to large n,in which we need to classify and discuss the generalized Petersen graphs in this process,so as to obtain the star chromatic index number.In Chapter three,we study the star edge coloring of subcubic graphs.Firstly,we give the infimum star chromatic index of Sierpinski graphs S(n,3),and a star edge coloring of the Sierpinski graphs S(n,3)according to the structure of it.It is easy to find the feasible infimum star edge coloring,and then we can determine its star chromatic index.Furthermore,we also study the cubic graphs.We construct a family of infinite cubic graphs based on a special cubic graph with star chromatic index 6.According to the construction process of the graph and the property of star edge coloring,we obtain that the star chromatic index of the graphs are 6.