Double Edge Coloring Problems Of Some Graphs

In this paper, all graphs are simple, undirected, connected, finite graphs. A graph is said to be embeddable in the plane, ox planar, if it can be drawn in the plane so that its edges intersect only at their ends. Such a drawing in the plane of a planar graph is called a planar embedding, and sometimes refered as a plane graph. A plane graph G partitions the rest of the plane into a number of connected regions; the closures of these regions are called the faces of G, and the unique unbounded face is called exterior face, and the others are called interior faces. For a plane graph G, we denote by V(G),E(G)andF(G), respectively, the vertex set, edge set and face set of G . Two faces f₁,f₂∈F(G) are adjacent if and only if f₁ and f₂ are incident with a common edge. The vertices and edges in the boundary of a face are said to be incident with it, and the number of the edges with which it is incident is called the degree of the face, (cut edge being counted twice), denoted by d_G (f). The maximumvalue of the degree of the face in G is called the maximum face degree of G, denoted by F_M(g); and the degree of the exterior face is denoted by F_ext(G), simultaneity, the maximum vertex degree and minimum vertex degree of G is denoted respectively byâ–³(G) andδ(G).The edge coloring with restriction of vertices and faces on a plane graph G, the double edge coloring, is defined as coloring the edges of G such that arbitrary adjacent edges are assigned with distinct colors and the edges in the boundary of a face are also assigned with distinct colors; The smallest number of colors such that G admits a double edge coloring is called double edge chromatic number, denoted byχ_e/vf(G). O. V. Borodin and D. R. Woodall presented first the concept of the doubleedge coloring, and had done the study about the double edge chromatic number for outerplane graphs, obtained a perfect result. In the paper, we consider the double edge chromatic number of some special types of planar graphs, such as approximate Halin graph, approximate outerplane graph, double outerplane graph, plane graph with high maximum degree,etc. For a plane graph G . ifδ(G)≥3 and that G is a tree aftertaking out the boundary of its exterior face, G is called the Halin graph. The approximate Halin graph is the non-Halin graph which has an edge e such that G-e or G·e is Halin graph. If all vertices of a plane graph G lie on the boundary of its outer face, then G is called the outerplane graph. The approximate outerplane graph is the non-outerplane graph which has an edge esuch that G-e or G·e is outerplanar. The plane graph that all vertices are situated on the boundary of two faces is called the double outerplane graph. A plane graph G is called an h_k -graph ifâ–³(G) =| V(G) |-k,k = 1,2,…, and G is called plane graph with high maximum degree when it = 1,2. If an h_k -graph G has no cut vertice, then G is called a p_k -graph.The paper is divided into five chapters. In Chapter One, we introduce some basic conceptions of graph theory, and summarize briefly the progress of the graph coloring theory and some primary results about the paper. In Chapter Two, after introduced the double edge coloring of Halin graphs, we discuss the double edge coloring problems for three types of approximate Halin graphs. In Chapter Three, we discuss the double edge coloring problems for two types of approximate t outerplane graphs. In Chapter four, we introduce the characteristic of double outerplane graphs, and discuss the double edge chromatic number of some special double outerplane graphs. In Chapter Five, we elementrily discuss the double edge coloring problems for special planar graphs with high maximum degree. The main results are the followings:Theorem 1: Let G be a almost Halin graph, and the superfluous edge e is situated intothe interior face of G-e, thenχ_e/vf(G) = F_ext(G).Theorem 2: Let G be a almost Halin graph, and the superfluous edge e is situated intothe exterior face of G-e, if G-e has a interior face which has attainedthe maximum face degree, thenχ_e/vf(G) = F_M(G).Theorem 3: Let G be the weak subdivision of Halin graph, thenχ_e/vf(G) = F_M(G).Theorem 4: Let G be a almost outerplane graph with a superfluous edge e, andG - e is rightly a outerplane graph which consists of a circuit plus exactlyone diagonal, then F_M (G)≤χ_e/vf(G)≤F_M(G) + 1.Theorem 5: Let G be a 2-connected maximum outerplane graph withâ–³(G) = 4,thenχ_e/vf(G)≤max{F_M(G) + 1,â–³(G) + 1}. Theorem 6: If G rightly consists of a circuit C_n plus exactly one k-diagonal path(n≥3,k≥1), thenχ_e/vf(G) = n + k≤3/2F_M(G),andχ_e/vf(G) = 3/2F_M(G) if and only if n = 2k and the diagonal path is a direct diagonal path.Theorem 7: Let G be the weak subdivision of a 2-connected outerplane graph, and G doesn't consist of a circuit plus exactly one diagonal path, thenχ_e/vf(G)=F_ext(G).Theorem 8: Let G be a 2-connected regular outerplane graph, thenχ_e/vf(G)≤F_M(G) + 1.Theorem9: Let G bea p₁-graph with |V(G)|≥6, thenχ_e/vf(G)≤F_M(G) + 1,andχ_e/vf(G) = F_M(G) + 1 if and only if G (?) P_â–³, illustrated by Figure5.1.1.Furthermore, in the last part of the paper we list some problems and a conjectureabout the double edge chromatic number of plane graphs for future research.