The Linear Arboricity, Equitable Colorings And Total Colorings Of Planar Graphs

Graph theory originated in 18th century. The earliest known paper is due to Euler (1736) about the seven bridges of Konigsberg. Since 1950s, with the rapid development of the computer science, graph theory has developed very fast and numerous results on graph theory appeared in a rash. The Four-Color Conjecture, the origin of graph coloring theory, always led the way in graph theory. And graph coloring has become a very important branch in graph theory. Graph coloring has important applications in optimization, computer science, network design and schedule, etc. The aim of this thesis is to discuss some colorings of graphs, such as linear arboricity, equitable coloring and total coloring.In this thesis, all graphs considered are finite and simple. For a planar graph G, let V(G), E(G), F(G) andΔ(G) denotes its vertex set, edge set, face set, and maximum degree, respectively. For a real number x,[x] is the least integer not less than x and [x] is the largest integer not larger than x.A properκ-total-coloring of a graph G is a coloring of V(G)∪E(G) using k colors such that no two adjacent or incident elements receive the same color. The total chromatic numberχ"(G) is the smallest integer k such that G has aκ-total-coloring. The chromatic numberχ(G) (or edge chromatic numberχ'(G)) of G is defined similarly in terms of coloring vertices (or edges) alone.A linear forest is a graph in which each component is a path. A mapφfrom E(G) to{1,2,…,t} is called a t-linear coloring if the induced subgraph of edges having the same color a is a linear forest for 1≤α≤t. The linear arboricity la(G) of a graph G defined by Harary in 1970 is the minimum number t for which G has a t-linear coloring. Here is a famous conjecture about the linear arboricity: Conjecture 1. For any graph G,[(?)]≤la(G)≤[(?)].Peroche proved that the determination of the linear arboricity of a graph G is an NP-hard problem, even whenΔ(G)=4. In this paper, we give the exact value of the linear arboricity of some restricted planar graphs.Another topic discussed in this thesis is equitable coloring. An equitable k-coloring of a graph G is a properκ-coloring, for which any two color classes differ in size by at most one. And if G has an equitableκ-coloring, we say that G is equitablyκ-colorable. The least integer k for which G has an equitableκ-coloring is defined to be the equitable chromatic number of G and denoted by Xe(G). In 1973, Meyer made the following conjecture (The Equitable Coloring Conjecture): Conjecture 2. For any connected graph G, except the complete graph and the odd cycle, Xe(G)≤Δ(G).In 1994, Chen, Li and Wu put forth the following conjecture: Conjecture 3. A connected graph G is equitablyΔ(G)-colorable if it is different from the complete graph Kn, the odd cycle C2n+1, and the complete bipartite graph K2n+1,2n+1 for all n≥1.Some results on conjecture 3 are given in this thesis.For total coloring problems, Behzad and Vizing posed independently the fa-mous conjecture, known as the Total Coloring Conjecture: Conjecture 4. For any graph G,Δ(G)+1≤χ"(G)≤Δ(G)+2.This conjecture has been unsolved completely. For planar graph G, the con-jecture has been confirmed whenΔ(G)≠6. Moreover, if G is a planar graph with maximum degreeΔ(G)≥9, thenχ"(G)=Δ(G)+1. In this thesis, we give the exact value of total chromatic of some planar graphs withΔ(G)≤8.This thesis is divided into four chapters. In Chapter 1, we introduce some basic definitions, notations, history of the colorings which we consider in this thesis and the main results. A short but relatively complete survey is given in the chapter.In Chapter 2, we consider the linear arboricity of planar graphs, and get the exact value of the linear arboricity of some planar graphs.Conclusion 1 Let G be a planar graph with maximum degreeΔ(G)≥5. If G doesn't contain 5-cycles and 6-cycles, then la(G)=[(?)]. Conclusion 2 Let i and j be two fixed integers (3≤i≤j≤5). If a planar graph G satisfies thatΔ(G)≥7 and any two cycles of length i and j, respectively, are not adjacent, then la(G)= [(?)].Conclusion 3 Let G be a planar graph withΔ(G)≥5. If any 4-cycle is not adjacent to an i-cycle for any i∈{3,4,5}, then la(G)= [(?)].In chapter 3, we investigate the equitable coloring of planar graphs. Employing the structures and properties of planar graphs and the technique of exchanging colors, we improve the result made by Zhang and Yap that a planar graph is equitably m-colorable for any 13≤Δ(G)≤m. It is improved to the case that A(G)> 10.Conclusion 4 Let G be a planar graph with maximum degreeΔ(G)≥10. Then G is equitably m-colorable for any m≥Δ(G).Conclusion 5 Let G be a planar graph withΔ(G)≥6 and without 3-cycles. Then G is equitably m-colorable for any m≥Δ(G).Conclusion 6 Let G be a planar graph withΔ(G)≥7 and without 4-cycles. Then G is equitably m-colorable for any m≥Δ(G).In chapter 4, we investigate the total coloring of planar graphs, and get the following results:Conclusion 7 Let G be a planar graph with maximum degreeΔ. IfΔ≥8 and G does not contain adjacent 4-cycles, then the total chromatic numberχ"(G)=Δ+1.Conclusion 8 Let G be a planar graph with maximum degreeΔ≥6 and without intersecting 4-cycles. If G doesn't contain 3-cycles, or 5-cycles, or 6-cycles, then the total chromatic numberχ"(G)=Δ+1.