| Graph coloring problem, one of the most important problems in graph theory, has wide applications in graph theory and theoretic computer science. In this thesis, we focus on edge colorings of multigraphs and several other colorings with constraint conditions of some simple graphs. Let G be a graph which might have multiple edges but no loops. Denote by V, E, △ and μ the vertex set, the edge set, the maximum degree and the multiplicity of G, respectively.In chapter 1, we will give the basic definitions of edge coloring, vertex coloring and some other colorings with constraint conditions. We also list the research progress and the corresponding conjectures of each coloring.The central problem in graph edge coloring lies in finding the exact value of chromatic index. A k-edge coloring φ of a graph G is a mapping from E to the set{1,2,…,k} (the elements are called colors), such that, no two adjacent edges receive the same color. The minimum k such that G has a k-edge coloring is called the chromatic index of G, and is denoted by x. To study edge coloring, it is easier to study fractional edge coloring. The fractional edge coloring of G is a nonnegative weighting w(.) of the set of matchings M(G) of G, such that for any edge e ∈ E, ∑∈M：e∈M:w(M)=1 It is easy to see that w(.) exists. The minimum total weight ∑∈M：e∈M:w(M) over all fractional edge colorings of G is called the fractional chromatic index, and is denoted by x’f. The computing of x’f is in polynomial time. The relationship between the chromatic index and fractional chromatic index of G is as follows:△≤x’f<≤x’≤ △+μ, where the upper bound is a classic result of Vizing. In fact, if x’f> △, then x’f=max|E(H)|/[|V(H)|/2] where the maximum is taken over all induced subgraphs H of G. Goldberg (1973), Andersen (1977) and Seymour (1979) independently conjectured that x’= [x’f] if x’≥ △+2. This conjecture is stronger than a conjecture posed by Gupta (1967) in his doctorial graduation thesis. And it is commonly referred as Goldberg’s conjecture or Goldberg-Andersen-Seymour’s conjecture. In chapter 2, we will show that if x’> △+3(?)△/2, then x’=[x’f].The previous best known result was for graphs with x’> △+(?)△/2 which is obtained by Scheide and by Chen, Yu and Zang, independently. It has been shown that Goldberg’s conjecture is equivalent to the following conjecture of Jakobsen:for any positive integer m with m≥ 3, every graph G with x’>m/m+1△+m-3/m-1 satisfies x’=[x’f].Jakobsen’s conjecture has been verified for m up to 15 by various researchers in the last four decades. We show that it is true for m≤ 23. Moreover, we show that Goldberg’s conjecture holds for graphs G with △< 23 or|V|≤ 23.A graph G is called simple if its multiplicity μ≤ 1. The k-vertex coloring φ of a simple graph G is a mapping from V to{1,2, …,k} (the elements are called colors), such that no two adjacent vertices receive the same color. The minimum k such that G has a k-vertex coloring is called the chromatic number of G. Since it is NP-hard to determine the chromatic number of G, we define, a relaxed case which is the tree coloring. A k-tree coloring φ of a simple graph G is an assignment of colors 1,2, …, k to the vertices of G, such that the subgraph induced by vertices of each color class is a forest. The vertex arboricity va of G is the minimum integer k such that G has a k-tree coloring. Wu, Zhang and Li consider the equitable tree coloring., i.e., a tree coloring such that the difference of the cardinalities of any two color classes is at most. one. They also conjectured that the vertex set of any simple graph G can be equitably partitioned into m subsets such that the subgraph induced by each subset is a forest, where m≥ [△+1/2] is an integer. In chapter 3, we will show that the conjecture is true for 5-degenerate graphs.If we delete the condition that any two adjacent edges receive different colors in the definition of k-edge coloring, then we obtain the definition of k-edge weighting. In 2004, Karonski, Luczak and Thomason conjectured that there exists a 3-edge weighting using colors 1,2,3 for any simple graph G, such that the sums of the incident edges of any two adjacent vertices are different. This conjecture is called the 1-2-3 conjecture. In chapter 4, we will prove that 1-2-3 conjecture is true when the vertex coloring induced by edge weighting is relaxed to be a tree coloring. Furthermore, we show some classes of graphs which have tree coloring 2-edge weightings.Neighbor sum, distinguishing k-edge coloring of a simple graph G is a k-edge coloring of G, such that for any edge uv ∈ E, the sum of edges incident with u is different from that of v. Denote by ndi∑ the minimum positive integer k for which G has a neighbor sum distinguishing k-edge coloring. Flandrin et al. conjectured that for any simple graph G with at least 6 vertices, we have ndi∑≤ △+2. This conjecture is called Neighbor sum distinguishing edge coloring conjecture. The maximum average degree of G is m.ad(G)= max{2|E(H)|/|V(H)|:H is a non-empty subgraph of G}. In chapter 5, we will prove that for any simple graph G without isolated edges and mad(G)< 8/3, we have ndi∑≤ k, where k= max{△+1,6}. It is an example of Neighbor sum distinguishing edge coloring conjecture.Chapter 6 is the conclusion of the thesis. We will give some problems in graph colorings for future works. |
PDF Full Text Request