Some Sufficient Conditions Of Class 1 Graphs On G_c-colorings

Let G be a graph, C be a color set. A proper edge coloring of G is an assignment of colors to edges of G such that adjacent edges receive distinct colors. An edge covering coloring of G is an assignment of C to edges of G such that each color of C appears at each vertex of G at least once. A gc-coloring of G is an edge coloring such that each color of C appears at each vertex v ?V(G) at least g(v) times, where g is a positive integer function defining on V(G). Clearly, a gc-coloring of G is a kind of extension of edge covering coloring. The maximum integer k such that G has a gc-coloring is called gc-chromatic index of G and denoted by ?gc'(G). A result of Huimin Song and Professor Guizhen Liu[18] shows that ?gc'(G)= ?_g(G)-1 or ?_g(G) for any simple graph, where ?_g(G)= minv?V(G){[d(v)/g(v)]}.We call G gc-class 1 if ?gc](G)=?_g(G), otherwise gc-class 2. The problem of determining the gc-chromatic index of a graph is called the problem of classification on gc-colorings. In this thesis, we discuss the classification problem on gc-colorings. We extend a result on edge covering colorings due to Xia Zhang and Professor Guizhen Liu[26] to gc-colorings, and obtain a new sufficient condition on gc-class 1 graphs by weakening the condition of the result. The new conclusion extends a result due to Huimin Song and Professor Guizhen Liu[18]. Moreover, we partly extend a result on proper edge colorings due to S. Akbari et al[l] to gc-colorings and get two sufficient conditions on gc-class 1 graphs.The thesis consists of four chapters.In Chapter 1, we introduce background and significance of this study, some notions and symbols to be used in this paper, and illustrate research progress on gc-colorings and our main results.In Chapter 2, we introduce some basic tools and give main lemmas to be used in the thesis.In Chapter 3, we give some class 1 graphs on gc-colorings and the proofs of the results.In Chapter 4, a problem for further research is presented.The main results of the thesis are as follows:Therorem 1 Let G be a simple graph, associate a positive integer function g: V(G)?Z+, and ?_g(G)?2. If G is weakly-?_g(G)-peelable, then G is of gc-class 1.Therorem 2 Let G be a simple graph, associate a positive integer function g: V(G)?Z+, and ?_g(G)?2. If G is not weakly-?_g(G)-peelable, but the DRRS of G has a general gc-coloring of ?_g(G) colors, then G is of gc-class 1.Therorem 3 Let G be a simple graph, associate a positive integer function g: V(G)?Z+, and ?_g(G)?2. Getting graph H from G by peeling off some vertices of G using weakly-?_g(G)-peeling operation. If degree restoration of H has a general gc-coloring of ?_g(G) colors, then G is of gc-class 1.Therorem 4 Let G be a connected simple graph, associate a positive integer function g:V(G)?Z+. If each component of G?_g is a unicyclic graph or tree, and the unicyclic graphs are not cycles, then G is of gc-class 1.Therorem 5 Let G be a connected simple graph, associate a positive integer function g:V(G)?Z+. If each component of G?_g is a unicyclic graph or tree, at most a unicyclic graph is a cycle and G?_g is not a cycle, then G is of gc-class 1.