Coloring Problems On Embedded Graphs

In1736, Euler published the paper named "The seven bridges of Konigsberg" in St Petersburg Academy of Sciences, which was the earliest known paper of graph theory. It inaugurated one branch of mathematics-Graph Theory. In the middle of the nineteenth century, Four-Color Conjecture was proposed. Then the coloring of graphs became one important research subject of graph theory. For more than one hundred years, Four-Color Conjecture has leading the development of graph theory. In1976, Appel and Haken proved this conjecture with computer. So Four-Color Conjecture became Four-Color Theorem. From then, graph theory which is as the footing stone of modern applied mathematics entered a period of rapid develop-ment. The graph coloring theory also has important application in Combinatorial Optimization, Theoretical Computer Science, Web Design, and so on. For exam-ple, files transmission in a computer network, computation of Hessians matrix. The aim of this thesis is to discuss some colorings of graphs and with their associated conjectures.In this thesis, all graphs considered are finite and simple. We use V(G), E(G), F(G),△(G) and δ(G)(or simply V, E, F,△and δ) to denote the vertex set, the edge set, the face set, the maximum degree and the minimum degree of G, respectively.Firstly, we study the total coloring of graphs. A proper k-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 x"(G) is the smallest integer k such that G has a κ-total-coloring. Clearly, x"(G)≥△+1. Behzad, and Vizing independently, posed the famous conjecture, known as the Total Coloring Conjecture (TCC):for any graph G,△+1≤x"(G)≤A+2. For planar graphs, the only open case is△=6. In this thesis, we proved this conjecture for the graph which can be embedded in a surface E of Euler characteristic x(Σ)≥0except△=6. Interestingly, the total chromatic number of planar graphs with large maximum degree equals the lower bound, i.e., x"(G)=△+1. This result was firstly given for△≥14. Later, W.F. Wang improved this result to△≥10. Now, this result was extended to△≥9. In this thesis, we proved this result to the graph which can be embedded in a surface E of Euler characteristic x(Σ)>0and with△≥9. In addition, for the planar graph with△=7,8, we got more interesting results.Secondly, we study the linear arboricity of graph. A linear forest is a graph such that each of its components is a path. The linear arboricity la(G) of a graph G as defined by Harary is the minimum number of linear forests in G, whose union is the set of all edges of G. In1980, Akiyama, Exoo and Harary posed the following conjecture:For any regular graph G, la(G)=[(?)].Clearly, la(G)≥[(?)]. So for every regular graph la(G)>[(?)].Hence, the conjecture above is equivalent to the linear arboricity conjecture:for any simple graph G,[(?)]≤la(G)≤[(?)]. Now, the linear arboricity conjecture was proved only for some graphs. In this thesis, we proved this conjecture to the graph which can be embedded in a surface E of Euler characteristic x(Σ)≥0. Recently, M. Cygan et al. posed the following conjecture:for any planar graph G of maximum degree△≥5, la(G)=[(?)]. They also proved this conjecture for△≥9. Here, we improved this result to the graph which can be embedded in a surface Σ of Euler characteristic x(Σ)≥0and with△≥9. In addition, for the planar graph with△=7, we got more interesting results.Lastly, we study the list edge and list total coloring of planar graphs. A mapping L is said to be a edge assignment for a graph G if it assigns a list L(x) of possible colors to each element x∈E. If G has a edge coloring cp such that t ψ(x)∈L(x) for all x∈E, then we say that G is edge-L-colorable or ψ is a edge-L-coloring of G. A graph G is edge-k-choosable if it is edge-L-colorable for every edge assignment L satisfying|L(x)|≥k for each x∈E. The list edge chromatic number x"_l (G) of G is the smallest integer k such that G is edge-κ-choosable. The list total chromatic number x"_l(G) of G can be defined similarly in terms of coloring the edges alone. It follows directly from the definition that x’_i(G)≥x’(G)≥△and x"_l{G)≥x"{G)≥△+1. List edge and list total colorings are two widely studied generalizations of the classical notions of graph coloring, and quite a few interesting results about these two colorings of planar graphs have been obtained in recent years. Now we introduce a famous conjecture: for any graph G,(a) x’_l(G)=x’(G),(b) x"_l{G)=x"{G). Combining with Vizing Theorem and TCC, we can get the following conjecture: for a graph G,(a)x’_l(G)≤△+1,(b)x"_l(G)≤△+2. Borodin et al. proved x’_l(G)=A and x"_l{G)=△+1for graphs with△≥12and which can be embedded in a surface of nonnegative characteristic. We will study the planar graph with small maximum degree and with cycle restrictions.Specifically, we have constructed our work in four chapters.A short but relatively complete introduction is given in Chapter1. First, we give some basic definitions and notations. Then, we describe some definitions and notations of classical coloring problems and introduce their histories, and list some associated conjectures. Last, we outline the main results of this thesis.In Chapter2, we consider the total coloring of graphs. First, for the graph embedded in a surface Σ of Euler characteristic x(Σ)≥0, if△≥7, then x"(G)≤A+2. This result shows the total coloring conjecture is only open for the graph embedded in a surface Σ of Euler characteristic x(Σ)≥0with A=6. In addition, for the graph embedded in a surface￡of Euler characteristic x(Σ)≥0, if△≥9, then x"(G)=A+1. We also give some results on planar graphs. For planar graphs with A>7and without adjacent4-cycles, then x"(G)=A+1. For planar graphs with A>8, if (a) every vertex v has two integers iv, jv∈{3,4,5,6,7,8} such that v is not incident with intersecting i_v-cycles and j_v-cycles, or (b) every vertex v has two integers iv,jv∈{3,4,5,6} such that v is not incident with adjacent i_v-cycles and j_v-cycles, or (c) every vertex v, the vertex v is not incident with chordal6-cycles, or chordal7-cycles, or2-chordal5-cycles, then x"{G)=△+1.In Chapter3, we consider the linear arboricity of graphs. First, for the graph embedded in a surface S of Euler characteristic x(Σ)≥0, we proved the linear arboricity conjecture is true. Moreover, for the graph embedded in a surface Σ of Euler characteristic x(Σ)≥0, if△≥9, then la(G)=[(?)]. We also give some results on planar graphs. For planar graphs with△≥5and without adjacent4-cycles, if G does not contain adjacent3-cycles and5-cycles, or intersecting3-cycles and4-cycles, then la(G)=[(?)]. For planar graphs with△≥7, if (a) every vertex v has two integers iv,jv∈{3,4,5,6,7,8} such that v is not incident with adjacent i_v-cycles and j_v-cycles, or (b) every vertex v has one integers i G {4,5,6,7} such that v is not incident with chordal i-cycles, then la(G)=[(?)].In Chapter4, we consider the list edge colorings and list total colorings of planar graphs. Let G be a planar graph with△≥7, we proved that if any4-cycle is not adjacent to an i-cycle for any i∈{3,4}, then x’_l(G)=△and x"_l(G)=△+1. In addition, we also prove x’_l{G)=△and x"_l{G)=△+1for the planar graph with△≥8and without adjacent4-cycles.