The F-Coloring And The Equitable Edge-Coloring Of Graphs

Graph coloring theory has a central position in graph theory. Among all kinds of branches of graph coloring theory, such as edge-coloring, vertex-coloring, face-coloring, total-coloring and so on, the edge-coloring is given most attention and has many perfect results. The aim of this thesis is to discuss some topics on edge-coloring problems, i.e. f-coloring, equitable edge-coloring and fractional f-coloring.In the thesis, all graphs considered are finite and undirected. They may have multiple edges but no loops. An edge-coloring of graph G is a partition of all the edges of G into edge-disjoint subsets. For the convenience of descriptions, we often call the subsets the color classes, and assign a distinct color to each color class. Let g, f be two integer-valued functions associated with each vertex of graph G such that 0≤g(v)≤f(v) for each v∈V(G). A (g, f)-factor F of G is a spanning subgraph of G such that g(v)≤dF(v)≤f(v) for all v∈V(G). A (g, f)-coloring of a graph G is an edge-coloring such that each subgraph induced by the edges colored with a same color is a (g, f)-factor of G. In particular, (0, 1)-coloring, (0,f)-coloring, (1,d)-coloring and (g, d)-coloring (where d = d(v) for each vertex v of G) are usually called proper edge-coloring, f-coloring, edge covering coloring and g-edge covering coloring, respectively.In 1986, Hakimi and Kariv [33] generalized the proper edge-coloring to the f-coloring and obtained many interesting results. The minimum number of colors such that G has an f-coloring is called the f-chromatic index of G and denoted by x'f(G). Obviously, if f(v) = 1 for all v∈V(G), the f-coloring problem, which is to determine X'f(G) of any graph G, is reduced to the proper edge-coloring problem. Holyer [42] proved that the proper edge-coloring problem is NP-complete, even when restricted to the class of cubic graphs. Therefore the f-coloring problem, which covers the proper edge-coloring problem as one of its subproblems, is also NP-complete. For a graph G, we write thatwhere [d(v)/f(v)] is the smallest integer not smaller than d(v)/f(v). In the proper edge-coloring, a well-known result of Vizing [79] says that for any simple graph G, x'(G) =â–³(G) orâ–³(G) + 1. With this result, all simple graphs are naturally partitioned into two classes. We say that simple graph G is of class 1 if x'(G) = A(G), and of class 2 otherwise. The problem of deciding whether a simple graph is of class 1 or class 2 is called the classification problem on proper edge-colorings. The classification problem on proper edge-colorings has been intensely studied. Significantly, as a consequence of a result of Hakimi and Kariv [33], there is a similar result on f-colorings of simple graphs, i.e. for any simple graph G, we have . Naturally, we can consider the classification problem on f-colorings. We say that graph G is of f-class 1 if and of f-class 2 otherwise. If f(v) = 1 for all v∈V(G), the classification problem on f-colorings is reduced to that on proper edge-colorings.Another topic discussed in this thesis is equitable edge-colorings of graphs. Let k≥2 be an integer and C = {c1, c2,..., ck} be a set of colors. Given an edge-coloring of G with k colors in C, for v∈V(G), let ci(v) denote the set of the edges incident with v colored with ci (1≤i≤k). Call an edge-coloring of G with k colors in C equitable if for every v∈V(G). The equitable edge-coloring problem is determining whether a given graph has an equitable edge-coloring with k colors for any integer k>2. We define Vt(G) = {v∈V(G) : t | d(v)}, where t is a positive integer. Call the subgraph of G induced by Vt(G) the t-core of G. Hilton and de Werra [39] studied the equitable edge-coloring problem on simple graphs, and presented some interesting results based on the k-core of a simple graph. Xu [91] considered the equitable edge-coloring of a graph and gave a sufficient condition for a graph to have an equitable edge-coloring with k colors. Set f(v) = [d(v)/k] for all v∈V(G). We can see that graph G has an equitable edge-coloring with k colors if and only if G has an (f - 1, f)-coloring with A; colors. Thus equitable edge-colorings of graphs have close relations with f-colorings or g-edge covering colorings of graphs. In this thesis, in virtue of some methods used in f-colorings, we obtain a new sufficient condition for a simple graph to have an equitable edge-coloring with k colors, which strictly covers a conjecture made by Hilton in [37]. Further, applying the new result to the edge covering coloring of a simple graph, we obtain an improvement of a result of Wang, Zhang and Liu in [83].The fractional graph theory is an important tool for studying all kinds of graph theory problems. We also apply it to the research on f-colorings of graphs. Then the third topic discussed is fractional f-colorings of graphs. Let G be a graph and f be a function which assigns a positive integer f(v) to each vertex v∈V(G). A (0, f)-factor F of G is a spanning subgraph of G with 0≤dF(v)≤f(v) for each v∈V(G). The edge set of a (0, f)-factor F of G is called an f-matching in G and denoted by F. A fractional f-coloring is an assignment of a nonnegative weight wF to each f-matching F of G so that for every edge e∈E(G) we have .The fractional f-chromatic index of G (where the sum is over all f-matchings F and the minimum is over all fractional f-colorings c). Many problems or conjectures unsolved in the (integer-valued) graph theory can be achieved concerning the fractional graph theory. The research on fractional f-colorings provides a new way for settling the f-coloring problem. Sometimes, a fractional f-colorings may be exactly an f-coloring desired.The thesis is divided into four chapters. In Chapter 1, we review the history and some progress of edge-coloring. In Chapter 2, we consider the classification problem on f-colorings and the properties of f-critical graphs. Firstly, we give a serious of sufficient conditions based on the f-core of G and two sufficient conditions on function f for a simple graph G to be of f-class 1. Secondly, we determine the f-chromatic indices of complete graphs and discuss the classification problem on f-colorings for simple regular graphs. Finally, we present a property of f-critical graphs. In Chapter 3, we show a new sufficient condition for equitable edge-colorings of simple graphs. This result verifies a conjecture made by Hilton [37] in 2005, and substantially extends it to a more general class of graphs. Also, we apply the new result on equitable edge-colorings of simple graphs to edge covering colorings of simple graphs, and obtain an extension of a result of Wang, Zhang and Liu [83]. In Chapter 4, we give the exact value of the fractional f-chromatic index of a graph. As a consequence, we prove the fractional version of the conjecture made by Nakano et al. in [62].Next, we will list our main results in this thesis.We define V₀^*(G) = {v∈V(G) : d(v)/f(v) =â–³_f(G)}. The f-core of a graph G is the subgraph of G induced by the vertices of V₀^*(G) and is denoted by G_â–³f. (If f(v) = 1 for all v∈V(G), the f-core of a graph G is the core of G.) In Chapter 2, firstly, we give a series of sufficient conditions for a simple graph G to be of f-class 1 based on the f-core of G.Conclusion 1 Let G be a simple graph. If V₀^*(G) = (?), then G is of f-class 1.Conclusion 2 Let G be a simple graph. If G_â–³f is a forest, then G is of f -class 1.We call a graph H edge-orderable, if the edges of H can be ordered e1, e2, ..., eε(H) in such a way that, for every j, 1≤j≤ε(H), edge e_j has an end vertex v_j such that, at every vertex u∈N_h(vj), there is an edge e_i with i≥j.Conclusion 3 Let G be a simple graph. If G_â–³f is edge-orderable, then G is of f-class 1.It is can be verified that a forest is edge-orderable. Therefore Conclusion 3 covers Conclusion 2. Given X (?) V(G) \ V₀^*(G), let H_X denote the subgraph of G defined by V(H_X) = V₀^*(G)∪X and E(H_X) = E(G_â–³f)∪E(X, V₀^*(G)), where E(X, V₀^*(G)) denotes the set of the edges joining vertices of X and vertices of V₀^*(G). A slightly more general result can be proved in virtually the same way. Conclusion 4 Let G be a simple graph. If there exists X (?) V(G) \ V₀^*(G) such that H_X is edge-orderable, then G is of f-class 1.The number d(v)/f(v) is called the /-ratio of vertex v in G, and denoted by d_f(v). A graph G isâ–³_f(G)-peelable, if all the vertices of G can be iteratively peeled off using the following peeling operation: Peel off a vertex v, which has at most one remaining neighbor of f-ratioâ–³_f(G). Then we have the following result.Conclusion 5 Let G be a simple graph. If G isâ–³_f(G)-peelable, then G is of f-class 1.The following result shows that Conclusion 5 covers Conclusion 4.Conclusion 6 Let G be a simple graph. If there exists X (?) V(G) \ V₀^*(G) such that H_X is edge-orderable, then G isâ–³_f(G)-peelable.Further, we show that Conclusion 5 is strictly stronger than Conclusion 4 by giving an example to present that the converse of Conclusion 6 does not hold. On the other hand, we have the following partial converse to Conclusion 6.Conclusion 7 Let simple graph G beâ–³_f(G)-peelable in such a way that the vertices in V₀^*(G) are all peeled first. Then G_â–³f is edge-orderable.In particular, when f(v) = 1 for all v∈V(G), we can deduce the results of Fournier [28], Hoffman et al. [41] and Hakimi et al. [34] based on the core of G.Secondly, in Chapter 2, we present two sufficient conditions on function f for a simple graph to be of f-class 1. Given a partial edge-coloring of graph G, we call a connected subgraph H of G an obstruction (to a partial f-coloring), ifε(H) is odd and d_H(v) = 2f(v) for each v∈V(H). Conclusion 8 Let G be a graph. If there is no obstruction in G, then X'f(G) =â–³_f(G).Clearly, if G is a simple graph, then G is of f-class 1. From Conclusion 8, we can easily derive two results of Hakimi and Kariv [33]. Moreover, we have the following result, which generalizes the simple graph version of a result of Hakimi and Kariv [33].Conclusion 9 Let G be a simple graph. Suppose that V₀^*(G)≠(?). If f{v) is positive and even for all v∈V₀^*(G)∪N_g(V₀^*(G)), then G is of f-class 1.We conclude that this condition is best in some sense.Thirdly in Chapter 2, we discuss the classification problem on f-colorings for two special kinds of simple graphs. We completely solve the classification problem on f-colorings for complete graphs.Conclusion 10 Let G be a complete graph K_n. If k and n are odd integers, f(v) = k and k | d(v) for all v∈V(G), then G is of f-class 2. Otherwise, G is of f-class 1.We write f* = min_v∈V(G){f(v)}. For simple regular graphs, we have the following results.Conclusion 11 Let G be a simple regular graph of degree d(G) =â–³. Then G is of f-class 1 if f^* (?)â–³or f^* is even.Conclusion 12 Let n≥1. Let G be a simple regular graph of order 2n + 1 and degree d(G) =â–³. Then G is of f -class 2 if f(v) =f^* is odd for all v∈V(G) andf^*|â–³. Conclusion 13 Let G be a simple regular graph of order n and degree d(G) =â–³, and G≠K_n. Suppose that w∈V(G) is the unique vertex such that f(w) > f^*. Then G is of f-class 1 if and only if G - w is of f-class 1.Conclusion 14 Let n≥1. Let G be a simple regular graph of order 2n and degree d(G) =â–³, where G≠K_2n. Let f(v) = f^* for all v∈V(G). Then G is of f-class 1 if and only if G - w is of f-class 1, where w∈V(G).Clearly, we can deduce the results in the classification problem on proper edge-colorings of complete graphs or simple regular graphs (see [11, 13]) from our Conclusions 10,12,14 when f(v) = 1 for all v∈V(G).Finally, in Chapter 2, we consider the properties of f-critical graphs. A simple graph G is called f-critical if G is of f-class 2 and x'f(G - e) < x'f(G) for every edge e∈E(G). We obtain the following result, from which Vizing's Adjacency Lemma [80] can be derived when f(v) = 1 for all v∈V(G).Conclusion 15 Let G be an f -critical graph and u, w be adjacent vertices of G. Then w is adjacent to at least f(w)(f(u)â–³f(G) - d(u) + 1) vertices of f-ratioâ–³f(G) different from u.And then, we get the following.Conclusion 16 Let G be an f-critical graph. Then each non-isolated vertex of G has at least two neighbors of f-ratioâ–³f(G), and G contains at least three vertices of f-ratioâ–³f(G).We also give another proof of Conclusion 5 by Conclusion 16.In Chapter 3, we consider equitable edge-colorings of simple graphs. Let M(v) denote the set of the colors each of which appears at most f{v) - 1 times at vertex v. We show a new sufficient condition for equitable edge-colorings of simple graphs as follows.Conclusion 17 Let G be a simple graph and let k≥2. Let f(v) = [d(v)/k] for each v∈V(G). Let C = {c1,c2,. ..., ck}. If the edges of G can be f-colored with k colors of C in the order e1, e2,..., eε(G) in such a way that, for every j (1≤j≤ε(G)), when f-coloring the jth edge ej = wjvj, there are M(v)≠(?) for all v∈Ng(wj) or for all v∈NG(vj), then G has an equitable edge-coloring with k colors.We find a much easier sufficient condition for a simple graph to have the properties described in Conclusion 17. We call a graph G t-peelable, if all the vertices of G can be iteratively peeled off using the following t-peeling operation: Peel off a vertex v, which has at most one remaining neighbor v' satisfied that v'∈Vt{G) and the degree of v' is still dG(v'). Then we have the following result.Conclusion 18 Let G be a simple graph and let k≥2. If G is k-peelable, then G has an equitable edge-coloring with k colors.This result covers the previous results, which are due to Hilton and de Werra [39], and verifies the following conjecture.Conjecture A (Hilton [37]) Let G be a simple graph and let k≥2. If thek-core of G is a forest, then G has an equitable edge-coloring with k colors.Also, with an example, we show that Conclusion 18 is strictly stronger than Conjecture A.The maximum number of colors such that G has an edge covering coloring is called the edge covering chromatic index of G and denoted by X'c(G). On the edge covering chromatic index of a graph, a well-known result of Gupta [31] says that for any simple graph G, X'c(G) =δ(G) orδ(G) - 1. Applying Conclusion 18 to edge covering colorings of simple graphs, we obtain a simple result immediately. Conclusion 19 Let G be a simple graph withδ(G) > 0. If G isδ(G)-peelable, then X'c(G) =δ(G).We consider a special kind of simple graphs. We call a graph G weak-δ(G)-peelable, if all the vertices of G can be iteratively peeled off using the following weak-δ(G)-peeling operation: Peel off a vertex v, which has at most one remaining neighbor v' satisfied that v'∈V(Gδ) and the degree of v' is stillδ(G). For weak-δ(G)-peelable simple graphs, we obtain a beautiful result as follows.Conclusion 20 Let G be a simple graph withδ(G) > 0. If G is weak-δ(G)-peelable, then X'c(G)=δ(G).This result strictly covers Conclusion 19, also is an extension of a previous result of Wang, Zhang and Liu [83].In Chapter 4, we consider the fractional f-coloring of graphs. Nakano et al. posed the following conjecture.Conjecture B (Nakano et al. [62]) If G is a graph, thenwhere in which v(H)≥2.We give the exact value of the fractional f-chromatic index of a graph.Conclusion 21 For any graph G, As a consequence of the above result, we prove the fractional version of Conjecture B. Also, we deduce many interesting results from Conclusion 21.In addition, we present some unsolved problems in Chapters 2, 3, 4, respectively.