Edge Coloring And Acyclic Edge Coloring Of Two Classes Of Graphs

More than one hundred years ago, the proposing of Four Color Problem became a milepost in the history of the development of graph theory, it created an important branch of graph theory, named the graph coloring theory. Graph coloring theory has a very important application in both daily life and theoretical research. Graph coloring theory has many branches, in this thesis, we study two classes of graph coloring problems, which are edge coloring and acyclic edge coloring.All graphs considered in this thesis are simple, undirected, finite and nonempty. Suppose that G is a graph, we use V(G), E(G), Δ(G),δ(G) and g(G)(or simply V, E, Δ, δ and g) to denote the vertex set, the edge set, the maximum degree, the minimum degree and the girth of G, respectively. A k-cycle is a cycle of length k. Given a cycle C of length k in G, an edge xy ∈ E(G)\E(C) is called a chord of C if x, y ∈ V(C). Such a cycle C is also called a chordal-k-cycle. Two cycles sharing at least a common edge are said to be adjacent. In this thesis, we mainly study the coloring problem of planar graph and 1-planar graph. If a graph G can be mapped on a plane such that any two edges of the graph intersect at the endpoints only, then we call it a planar graph. The mapping which satisfies the above conditions is called the planar embedding of the graph G. The pattern of planar embedding of the planar graph is called plane graph. We use F(G) to denote the face set of planar graph. If a graph G can be mapped on a plane such that each edge is crossed by at most one other edge, then we call it 1-planar graph.In this thesis, we mainly adopt the discharge method to solve the coloring problem of some graphs. Discharge method is one of the important tools in the study of graph theory, its role is particularly reflected in the study of the structure and coloring of the planar graph. The difficulty of this thesis is the designment of discharging rules. Firstly, we design a general discharging direction which makes the charge of most of the vertices and faces of the graph G to be more than or equal to 0 after redistribution. Then we according to the actual situation, design a special discharging rule for vertices who’s charge are still less than 0, the new charges of these vertices may come from the relatively small some neighbors, or the neighbors of neighbor. Lastly, we prove that the discharging rules is with the requirements.Let G = (V, E). A k-edge-coloring of G is a mapping φ:E â†'{1,2, … , k}. If every two adjacent edges in G receive different colors under φ, then we call φ a proper k-edge-coloring. A graph is k-edge-colorable, if it has a proper k-edge-coloring. The edge chromatic number of a graph G, denoted by χ’(G), is the smallest integer k such that G is k-edge-colorable. In 1964, Vizing proved a famous theorem- Vizing theorem:For any simple graph G, Δ(G)≤χ’(G) ≤ Δ(G)+1. Vizing theorem divided all simple graphs into two classes:A graph G is said to be of class 1 if χ’(G)=Δ(G), and of class 2 if X’(G)=Δ(G)+1.This thesis consists of four parts. The chapter 1 is a general introduction of the whole thesis. In the section 1, we give some definitions and notations used in the thesis. In the section 2, we introduce the two classes of coloring problems, namely, the edge coloring and acyclic edge coloring of graph. In the section 3, we introduce in detail the research methods used in this thesis, which is the discharge method. We also give concrete examples to illustrate the specific operation steps of the method. In section 4, we list the main results obtained in this thesis.In chapter 2, we first introduce the research status of edge coloring of planar graphs:For edge coloring of planar graphs, it is unable to determine whether a planar graph with maximum degree 6 belongs to class 1. But there are some results about planar graphs (Δ≥6) with restrictive conditions. Then we give some important lemmas which are used in the process of proof. Finally, we show in detail the conclusions we have obtained in four sections. The four conclusions of this chapter are as follows:Conclusion 1. If every 6-cycle contains at most two chords, then G is of class 1.Conclusion 2. If every 7-cycle contains at most two chords, then G is of class 1.Conclusion 3. If G contains no adjacent 7-cycles, then G is of class 1.Conclusion 4. If G contains no adjacent 8-cycles, then G is of class 1.In chapter 3, we first introduce the research status of 1-planar graph and its various coloring, then we study the edge coloring of 1-planar graph. The edge coloring problem of 1-planar graph is first proposed by Xin Zhang and Jianliang Wu, and they proved that every 1-planar graph with maximum degree Δ≥10 is of class 1. In addition, they also constructed class 2 1-planar graphs with maximum degree 6 or 7, so they posed the following conjecture:Every 1-planar graph with maximum degree at least 8 is of class 1. For the edge coloring of 1-planar graphs, it is unable to determine whether a 1-planar graph with maximum degree 8 or 9 belongs to class 1. But there are some results about 1-planar graphs(Δ≥8) with restrictive conditions. In this chapter, We also use the discharge method to study the edge coloring of some 1-planar graphs. Firstly, we need to have an operation on the 1-planar graph G:embedding G in a plane such that every edge is crossed by at most one other edge and the number of crossings is as small as possible and turning all crossings of G into new 4-vertices, the resulting graph is a planar graph. We call this graph associated plane graph, denoted as G×. In the following, we obtained a contradiction by using discharge method on G×, which complete the proof. In section 2,3,4 of this chapter, we obtain three results on edge coloring of 1-planar graphs:Conclusion 5. Suppose that G is a 1-planar graph with Δ> 8. If G contains no adjacent 4-cycles, then G is of class 1.Conclusion 6. Suppose that G is a 1-planar graph with Δ> 8. If G contains no 5-cycles, then G is of class 1.Conclusion 7. Suppose that G is a 1-planar graph with Δ> 9. If G contains no adjacent chordal 5-cycles. then G is of class 1.Lastly, in chapter 4, we study the acyclic edge coloring of planar graphs. In section 1, we introduce the definition of acyclic edge coloring and its research status. Given a proper edge coloring of G, a cycle is called bichromatic if only two colors appear on the cycle. An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index a’(G) of a graph G is the minimum number k such that G admits an acyclic edge coloring using k colors. A graph G is acyclically edge k-colorable, if G admits an acyclic edge coloring using at most k colors. In 2001, Alon, Sudakov and Zaks posed a famous conjecture which is called the Acyclic Edge Coloring Conjecture:For any graph G, a (G)≤Δ(G)+2. This conjecture was verified for some special classes of graphs. In addition, this conjecture was also proved for some planar graphs with restrictive conditions. The section 2 is the proof of the conclusion in this chapter. In the process of proof, we have an operation on G:to delete all of its 2-degree point and get a subgraph H. In the following, we obtained a contradiction by using discharge method on H, which complete the proof. We get the results on the acyclic edge coloring conjecture as follows:Conclusion 8. Suppose G is a planar graph. If for every vertex v, there is an integer kv ∈{3,4,5} such that v is not incident with any kv-cycle, then a’{G)≤Δ(G)+2.