Two Kinds Of Vertex-distinguishing Of Edge Coloring Graphs And Its Chromatic Number Estimation

This thesis is devoted to study the graph coloring problems, the coloring ofgraph is one of the signifcant branches in graph theory.This thesis introduce some concepts of D(2)-vertex-distinguishing star edge col-oring, vertex-distinguishing star edge coloring. Furthermore vertex-distinguishingacyclic edge coloring of graphs is studied and some upper bounds of these chromaticnumbers are obtained by the Lovász general local lemma, respectively. This thesisconsists of fve chapters.The frst chapter of this thesis is preface, a short but relatively complete intro-duction is given.In the second chapter, some preliminaries, such as basic concepts and lemmaswhich are incident to probabilistic method, are given.In the third chapter, the concept of D(2)-vertex-distinguishing star edge color-ing of graphs is introduced. One upper bound for D(2)-vertex-distinguishing staredge chromatic number of graphs which satisfy certain conditions is presented byprobabilistic method.In the fourth chapter, the concept of vertex-distinguishing star edge coloringof graphs is presented, and the vertex-distinguishing star edge chromatic numbersof some simple graphs-the path Pn, the cycle Cn, the wheel Wn, the fan Fnaregiven by using of the method of constructing concrete coloring. An upper boundfor the vertex-distinguishing star edge chromatic number of graphs is introduced byprobabilistic method.In the ffth chapter, the vertex-distinguishing acyclic edge coloring of Kp,pare discussed, and an upper bound for vertex-distinguishing acyclic edge chromatic num-ber of graphs which satisfy certain conditions is ofered by probabilistic method.