The Relationship Between The F-chromatic Class And The G_c-chromatic Class Of A Nearly Regular Graph

Let G be a graph and C be a color set. An edge-coloring of G is an assignment of colors to all the edges of G. A proper edge coloring of G is an edge-coloring of G such that adjacent edges receive distinct colors. An edge covering coloring of G is an edge-coloring of G such that each color of C appears at each vertex of G at least once. Let f and g be two functions which assigns a positive integer f(v) and a nonnegative integer g(v) to each vertex v ? V(G), respectively. An f-coloring of G is an edge-coloring of G such that each vertex v ? V(G) has at most f(v) edges colored with the same color. A g_c-coloring of G is an edge-coloring of G such that each color appears at each vertex v ? V(G) at least g(v) times. Clearly, a graph G has a g_c-coloring if and only if 0 ? g(v) < d(v) for each v ? V(G). In this paper,we always assume that 0 ? g(v) ? d(v) for each v ? V(G). The minimum number of colors needed to f-color G is called the f-chromatic index of G and denoted by X'f(G),and the maximum number of colors needed to g_c-color G is called the g_c-chromatic index of G and denoted by x'g_c(G). The f-coloring is exactly the proper edge-coloring when f ? 1,and the g_c-coloring is exactly the edge covering coloring when g ? 1. Since the proper edge-coloring problem is NP-complete (even if for cu-bic graphs), the f-coloring problem and the g_c-coloring problem are NP-complete,too. Hakimi and Kariv firstly posed that X'f(G) = ?(G) or ?f(G) +1 for any sim-ple graph, where ?f(G) =(?). We call G f-class 1 if X'f(G) = ?f(G),otherwise f-class 2. The problem of determining the f-chromatic index of a graph is called the problem of classification problem on f-colorings. A result of Huimin Song and Guizhen Liu shows that X'g_c(G) = ?g(G) or ?g(G)- 1 for any simple graph,where ?g(G) =(?). We call G g_c-class 1 if X'g_c(G) = ?g(G), otherwise g_c-class 2. The problem of determining the g_c-chromatic index of a graph is called the problem of classification problem on g_c-colorings. In this thesis, we discuss the classification problem on f-colorings for nearly regular graphs and the relationship between the f-chromatic class and the g_c-chromatic class of a nearly regular graph.Xia Zhang proved that there are always coincident classification results betweenthe f-chromatic class and the g_c-chromatic class for any regular graph G when the f-core and the g_c-core of G are same and f(v) = g(v) for each v of the f-core (the g_c-core). However, it is not always true for the other graphs (even if for nearly reg-ular graphs). In this thesis, we give some sufficient conditions for a nearly regular graph has coincident classification results between the f-chromatic class and the g_c-chromatic class when the f-core and the g_c-core of G are same and f(v) = g(v)for each v of the f-core (the g_c-core).This article consists of four chapters. In the first chapter, we introduce the research background and significance, give the basic notions and symbols to be used in this thesis, and illustrate research progress on the relationship between the f-chromatic class and the g_c-chromatic class of some types of graphs and our main results on a nearly regular graph. In the second chapter, we introduce some pre-liminary knowledge to be used in the thesis , including the main tools and main lemmas. In the third chapter, we discuss the relationship between the f-chromatic class and the g_c-chromatic class of a nearly regular graph. We give first some results on the f-chromatic class of a nearly regular graph. Some results on the relation-ship between the f-chromatic class and the g_c-chromatic class are given when the vertices of the f-core and the g_c-core contained by the r-degree set, (r + 1)-degree set, respectively. In the fourth chapter, a problem for further research is presented.