On G_c-colorings Of Some Classes Of Graphs

Let G be a simple 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 colors 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 with the colors in set C satisfying that, for each vertex v ?VG)and each color c?C, there are at least g(v) adjacent edges colored with color c,where g is a nonnegative integer function on V(G) with 0 ? g(v) ?d(v) to each vertex v? V(G).The gc-chromatic index of G, denoted by?gc'(G), is the maximum number of colors such that a gc-coloring of G exists. A result of Huimin Song and Guizhen Liu in 2005 showed that any simple graph G has the gc-chromatic index equal to ?g(G) or ?g(G) - 1, where ?g(G)=(?). We say that a graph G is of gc-class 1 if ?gc'=?g(G), and G is of gc-class 2 otherwise. The problem deciding whether a graph G is of gc-class 1 or gc-class 2 is called the classification problem on gc-colorings. In this paper, we mainly study the gc-coloring of some classes of graph-s. Firstly, we study some properties of gc-critical graphs, we find a new necessary condition for gc-critical graphs,which strictly generalizes a result of Jihui Wang et al. in 2007 and a result of Huimin Song and Guizhen Liu in 2004. Secondly, we s-tudy gc-colorings of nearly bipartite graphs. We give some new sufficient conditions for a nearly bipartite graph to be of gc-class 1. Our results generalize some pre-vious results due to Jihui Wang et al. in 2006 and Jinbo Li and Guizhen Liu in 2011.The thesis consists of four chapters. In chapter 1, we introduce the background and significance of this study, some basic concepts and symbols to be used in this paper, expound the edge covering coloring and gc-coloring theory research and list the main results of this thesis. In chapter 2, we introduce the basic research tools,some important lemmas and corollaries to be used in this thesis. In chapter 3, we study the gc-coloring of some classes of graphs and give the main results and their proofs. In chapter 4, we give some further research problems.