Some Results On Edge Partitions Of Planar Graphs

All graphs considered in this paper are finite simple graphs. Let G = (V(G), E(G)) be a graph, where V(G) and E(G) denote the vertex set and edge set of G, respectively. We use d_G(v) to stand for the degree of v in G. Let A(G) and 5(G) denote the maximum and the minimum vertex degree of G, respectively. For any S (?)V(G), the remaining subgraph of G obtained by deleting all the vertices in S and all the edges incident with the vertices in S is denoted by G — S. If S = {v}, v ∈ V(G), we usually denote G-v = G- {v}. For any X (?) E(G), the remaining subgraph of G obtained by deleting all the edges of X is denoted by G - X. If X = {e}, e ∈ E(G), we usually denote G-e = G- {e}. We call a graph G a bipartite graph if the vertex set of G can be partitioned into two subsets X and Y, so that each edge has one end in X and the another end in Y, such a graph is denoted by G = (X, Y, E(G)).If a graph G can be drawn in the plane so that each pair of edges intersect only at their ends, it is said to be a planar graph. Such a drawing of a planar graph G is called a planar embedding of G, or a plane graph. We shall denote the set of faces of a plane graph G by F(G). The boundary of a face f of a plane graph is the set of edges that surround f, and f is said to be incident with the vertices and edges in its boundary. Similarly, we can define the degree, d_G(f), of a face f as the number of edges with which it is incident, cut edges being counted twice. The faces f₁ and f₂ are said to be adjacent at edge e when e is one of the common edges of their boundaries.A graph G is said to k -edge-colorable when there is a function Φ : E(G) → {1,2, … ,k} such that, for each two adjacent edges e₁ and e₂, Φ(e₁)≠φ(e₂). Therefore, for each 1 ≤ i ≤ k, the edge-induced subgraph of φ^-1(i) is a matching of G. The edge chromatic number of a graph G, denoted by x'(G), is the smallest integer k such that G is k-edge-colorable.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 α is a linear forest for 1 ≤ α ≤ t. The linear arboricity la(G) of a graph G is the minimum number t for which G has a t-linear coloring.The theory of graph coloring is one of the most important branches in graph theory. Partitioning a set of objects into classes according to certain rules is a fundamental process in mathematics. A conceptually simple set of rules tells us for each pair of objects whether or not they are allowed in the same class. The theory of graph coloring deals with exactly this situation, and is full of interest for its applications. Time tabling, scheduling, and sequencing problems, in their many forms, are basically of this nature.The origins of graph coloring theory may be traced back to 1852 with the appearance of the famous 'four-color conjecture' . The theory of edge coloring has received less attention until relatively recently. However, much studied areas, such as map coloring, matching theory, and Latin squares, have strong connections to edge colorings. The first papers involving edge colorings appeared in 1880. In these papers P. G. Tait outlined some further 'proofs' of the four-color conjecture, and deduced that the edges of every cubic map can be colored with just three colors in such a way that the three edges meeting at each vertex are assigned different colors. Following Tait, there are some other outstanding results which are related to edge colorings, and had completely changed the state of knowledge in the subject. These results are Konig's Theorem, Shannon's Theorem, Vizing's Theorem, and so on. According to the famous theory of Vizing, graphs can be partitioned into two classes. The classification problem is the problem of deciding whether G is of Class 1 or of Class 2. Although some results of the classification problem have been gotten, there are still many remaining problems unsolved. In the field of the research of planar graphs, Vizing proved that every planar graph G with â–³(G) ≥ 8 is of class one. Furthermore, there are planar graphs of class two for each △∈{2,3,4,5}. And then he raised the famous Planar Graph Conjecture.The concept of linear arboricity is defined by Harary in 1970. And then, in 1980, Akiyama, Exoo and Harary conjectured that la(G) = for any regular graph G. This conjecture is equivalent to the Linear Arboricity Conjecture for arbitrary graphs. During the research of the linear arboricity, J. Wu solved a majority of the conjecture for planar graphs, remaining the case â–³ = 7 unsolved.In this paper, we'll try to give some results about the edge coloring and the linear arboricity of planar graphs. The paper is divided into three chapters. In Chapter One, we introduce some basic conceptions of graph theory, the history and some new advances on edge colorings and linear arboricities. This chapter is the base of following chapters.Chapter Two is major in edge colorings of planar graphs. The main results are the following theorems.Theorem 2.1.10. Let G be a planar graph with â–³(G) = 5. If G contains no 4-cycle or 5-cycle, then G is of class one.Chapter Three gives some results about the linear arboricity of planar graphs. The main results are as following:Theorem 3.2.1. Let G be a planar graph with maximum degree â–³ = 7. Then la{G) ≤ 4.Theorem 3.3.2. If G is a planar graph with â–³(G) ≥ 11, then la(G) = Theorem3.3.3. Suppose that G is a planar graph and two 3-cycles are not adjacent. If â–³(G) ≥ 7, then la(G) =...