Some Topics On Edge Cover Coloring Problems Of Graphs

The study of graph theory started over two hundreds years ago. As early as 1736, Eulcr used the methods of graph theory to solve the problem of the famous seven bridges of Konigsberg. With modern manufacturing and the development of science and technology, graph theory has been widely used. Graph theory has become an important subject of modern mathematical science. Induced by the Four-Color Conjecture, graph coloring theory has a central position in graph theory. The coloring theory of graphs is an important branch of graph theory. Graph coloring has interesting real-life applications in computer science, optimization and network design, such as computation of Hessians matrix, file transfers in a computer network and so on. The coloring theory has many kinds, such as edge coloring, vertex coloring, face coloring, total coloring and so on. Among them, the edge coloring is given most attention and has many perfect results. The proper edge coloring is to divide the edge set of G into some disjoint independent edge sets. In proper edge coloring theory, the Vizing's Theorem and the classification problem arc well known. Recently, many authors consider the generalization of proper edge coloring, that is, we can consider other forms in which we can divide the edge set. The aim of this thesis is to discuss some topics on edge coloring problems such as edge cover coloring,f-edge cover coloring, fractional f-edge cover coloring of graphs.Let G(V(G),E(G)) be a graph with vertex set V(G) and edge set E(G). If S is a set, we shall denote by|S| the cardinality of S. Throughout this thesis the term graph is used to denote a simple graph G with a finite vertex set V and a finite edge set E. If multiple edges arc allowed, G is called a multigraph. For a vertex v of G, the degree of v in G is denoted by dG(v). Let NG(v) denote the set of neighbors of vertex v. We writeδ(G)=min{dG(v):v∈V(G)} andΔ(G)= max{dG(v):v∈V(G)} to denote the minimum degree of G and the maximum degree of G, respectively. If there is no confusion, we use V, E, N(v),δ,Δinstead of V(G), E(G), NG(v),δ(G),Δ(G), respectively.G is regular ifΔ(G)=δ(G)= d, we also say that G is d-regular. A graph is cubic if it is 3-regular. A graph G is bipartite if there exists a partition (V1, V2) of V(G) such that each edge of G joins a vertex of V1 to a vertex of V2.A nearly bipartite graph is a graph G with a vertex u of G such that G-u is a bipartite graph with bipartition (X, Y), denoted by G(X, Y;u). G is a join graph if G is the complete union of two graphs G1= (V1, E1) and G2=(V2, E2).Assume that a positive integer f(v) with 1≤f(v)≤d(v) is associated with each vertex v∈V. We associate positive integer 1,2,…, k with colors, and we call C a k-cdge coloring of G if C:E→{1,2,…, k}. Let ci(v) denote the number of edges of G incident with vertex v that receive color i by the coloring C. We call C an f-edge cover coloring of G if for each vertex v∈V and for each color i=1,2,…, k,ci(v)≥f(v), that is each color appears at each vertex v∈V at least f(v) times. Letχ'fc(G) denote the maximum number of colors for which an f-edge cover coloring of G exists. We callχ'fc(G) the f-edge cover chromatic index of G.Letδf=(?){(?)d(v)/f(v)(?)}. It is known thatδf-1≤χ'fc(G)≤δf.From the above conclusion, we can see that the f-edge cover chromatic index of any graph G must be equal toδf orδf-1. This immediately gives us a simple way of classifying graphs into two types according toχ'fc(G).More precisely, we say that G is of fc-class 1 ifχ'fc(G)=δf, and that G is of fc-class 2 ifχ'fc(G)=δf-1. If f(v)= 1 for all v∈V, thenδf=δand f-edge cover coloring is reduced to edge cover coloring. Correspondingly, we have edge cover chromatic indexχ'c(G) such thatδ-1≤χ'c(G)≤δ,and the classification problem on edge cover coloring is that G is of C1-class ifχ'c(G)=δ, and that G is of C2-class ifχ'c(G)=δ-1. In general, the problem of determining the edge cover chromatic index of graphs is NP-complete because deciding whether a 3-connected cubic graph G is proper 3-edge colorable is N P-complete, which is the special case of our general problem. But it is possible to determine the value ofχ'c(G) of some special graphs. In classification problem, the conception of "critical" is very important. Let G be a connected and not complete graph withχ'fc(G)=δf-1. If for any u,v∈V and e=uv(?)E, there isχ'fc(G+e)=δf,then G is called an f-edge covered critical graph. Similarly, if f(v)=1 for all v E V, we also have the edge covered critical graphs. The properties of f-edge covered critical graphs are important for the classification problem on f-edge cover coloring.Fractional graph theory is an important branch of graph theory. Fractional edge coloring and fractional edge cover coloring are all relatively new research directions, they play an important role to the research of the proper edge coloring and edge cover coloring of graphs. In this paper, we first proposed the concept of fractional f-edge cover coloring of graphs. It has an important role in the discussion of the f-edge cover coloring of graphs. Therefore, the discussion of fractional f-edge cover coloring is also very meaningful.A fractional f-edge cover coloring is an assignmentωof nonnegative weights to the set of f-edge covers of G such that for each e E E(G) we have∑F(?)eωF≤1. Then the fractional f-edge cover chromatic index of graph G,χ'fcf(G),is the maximum value of∑FωF,where the sum is over all f-edge covers F and the maximum is over all fractional f-edge cover coloringsω.We can find that the results on edge cover coloring are correspond with those of proper edge coloring. But we can not deduce them from each other. The research methods are very different and the method of reserch for edge cover coloring is very difficult.This thesis is concerned with some topics on edge colorings of graphs. More specifically, our aim is to discuss edge cover coloring,f-edge cover coloring, frac-tional f-edge cover coloring and so on. We have constructed our work in four chapters.In Chapter 1, we firstly give some basic definitions and notations. Then we de-scribe some definitions and research history of the colorings which we will consider in this thesis. At last, we outline the main results of this thesis.In Chapter 2, we consider the classification of the edge cover coloring of graphs. Some sufficient conditions for a graph to be Cl-class or C2-class are given. We described various ways of constructing critical graphs for edge cover colorings. The classification for some special graphs are discussed. Some new results are detained.In Chapter 3, we introduce some definitions and progresses of f-edge cover coloring of graphs. We consider f-edge cover coloring of regular graphs and nearly bipartite graphs, and give some sufficient conditions for a graph to be of fc-class 1. Some properties on f-edge cover critical graph are discussed.In Chapter 4, we discuss the fractional f-edge cover coloring of graphs. We give an exact formula of fractional f-edge cover chromatic index of G,χ'fcf(G).Set and We have...