On The Colorings Of Double-outer Planar Graphs

The colorintgs of the graphs is one of the main problem in studying graph theory. In general,the colorings of the graphs is divided into vertice-coloring ,edge-coloring, and total coloring.The main purpose of the present paper is to investigate the edge chromatic number X′(G) and the total chromatic number X_T(G) of double outerplanar graph withΔ(G)≥6.All graphs considered in this paper are finite, simple and undirected. For a graph G ,we denote by V(G),E(G),Δ(G), and δ(G)the vertex set ,the edge set of G,themaximum(vertex) degree and the minimum (vertex) degree of G Let v(G) andε(G) denote the number of vertices and the number of edges . The degree of thevertex is d_G(v). If v∈ V(G),N_G(v) denotes the set of vertices adjacent to v. LetG(V′) denote the induced subgraph of G with vertex set V′ and G(E′) denote theinduced subgraph of with edge set E'. The weight of a edge is denoted by w(e).The length of a circle is denoted by C_n .Let σ(y) denote the color assigned to theelement y∈V(G)∪E(G) in a given coloring σ,and let E_σ(u)denote the set ofcolors used on the edges incident to the vertex u underσ.The edge chromatic number of G is denoted by X′(G) ,The total chromatic numberis denoted by X_T .Notations and definitions not given in this paper can be found in[1].A planar graph is a graph which can be embedded in the plane in such a way that no two edges intersect geometrically except at a vertex to which they are both incident. Ifa connected graph G is embedded in the plane in this way , it is called a plane graph; in this case, the points of the plane not on G are partitioned into open regions called faces.Let G(V,E,F) be a planar graph,where V(G),E{G),andF(G) are the set ofvertices the set of edges and the set of faces of G, respectively. Two vertices in V(G) are adjacent if they are joined by an edge, two edges in E(G) are adjacent if they have a common vertex and two faces in F{G) are adjacent if their boundaries haveat least one common edge. We say that a vertex (an edge) is incident to a face if it forms part of the boundary of the face. Also the verties u and v are each incident to the edge uv.This paper is divided into four chapters. In Chapter 1, We introduce some basic conceptions of graph theory, the history of the colouring and the progress on the edge colouring and the total colouring.In section 1,general terms and related conceptions are given. In section 2, we review the conceptions of planar graph and outerplanar graph .we define the double outerplanar graph.In section 3, we review the conjecture and progress of the edge coloring ,the total coloring .and the results of the edge coloring and total coloring.Definition 1.2.1 If all the vertices of planar graph G are located in the boundary of the unbounded face. Then this graph is called an outerplanar graph .The unboundedface, denoted by f0 (G) is called outside face . and other faces inside faces;the edgeson the boundary of outside face are said to be outside edges . and other edges insideedges.Definition 1.2.2 If all the vertices of planar graph G are located in the boundary oftwo face .Then this graph is called a double outerplanar graph . The two face, denotedby Fo ={/(,,/, }* are called outside face. And other faces inside faces .denoted, byF\F0.Definition 1.3.1: A planar graph G is k-edge colorable.if the elements of ￡(G)canbe colored with k colors such that any two distinct adjacent elements receive differentcolors. A planar graph G is k-total colorable, if the elements of V(G) u E(G) can becolored with k colors such that any two distinct adjacent of incident elements receive different colors.Definition 1.3.2: The edge chromatic number /(G) of G is defined as the minimum number k for which G is k-edge colorable.The total chromatic number %T(G) is defined as the minimum number k for which G is k-total colorable.In order to study the structure of double outer planar graph beater ,we give some definition in section 1 of chapter 2.Definition 2.1.1 The edge-face dual of planar graph GEF ,V{GEF) = E(G)uF(G) E(GEF) = {(eJ):e€E(G),feF(G)} and e isincident to a face f.In [3], Zheng dong ling and Wu jian Hang define weak dual of outerplanar graph:Definition 2.1.2 If G is any connected outerplanar graph ,we define a dual GWF of G in the following way : ( 1 ) take a plane embedding of G, and place one point in each inside face of G— these points are the vertices of GF ; (2) for each edge e of Gdraw a line crossing e and joining the two vertices of GF which lie in the facesseparated by e —these lines are the edges of G*.As the same method , we can define the weak dual of the double outerplanargraph.Definition 2.1.3 Let G is a double outerplanar graph ,(1) take a plane embedding ofG and place one point in each inside face of G— these points are the vertices ofGF; (2) for each edge e of G draw a line crossing e and joining the two vertices of GZ which lie in the faces separated by e —these lines are the edges of GF .thenG" is called weak dual of double outerplanar gaph.Definition 2.1.4: The edge-face weak dual of outerplanar graphGef = Gef ^fo> fo^s unbounded face of outerplanar graph G; The edge-face weak dual of double outerplanar graph GgF =GFF \{/0,/ }. f0 ,fx is twooutside face of double outerplanar graph GIn chapter 2 ,section 2 we study dual structure of double outerplanar graph ,we obtainted the following results.Property 1: The weak dual of a double outerplanar graph(and the edge-face weak dual of a double outerplanar graph) is a graph which have at most a cycle.Property 2 : Let G be a 2-connected double outerplanar graph of A(G) > 6 ,Then one of the following conditions holds(1) There is an edge e = uv with d(u) + d(v) < 7,that is w(e) < A(G) +1; or(2) There is a cycle v,v2"-v2nv, with d(v1) = d(v3) = -d(v2n_l) = 2Chapter 3 is major results we obtained, In section 1, Using the property 2 we discuss the edge coloring of double outerplanar graph ,we have the following results:Theorem 1: Let G be a 2-connected double outerplanar graph of A(G ) > 6 ,ThenIn section 2,Using the property 2 we discuss the total coloring of the double outerplanar graph ,we have the following results:Theorem 2: Let G be a 2-connected double outerplanar graph of A (G ) > 6 .ThenIn Chapter 4,we list some problems for future research.