The Vertex Coloring Problem Of Double-outer Planar Graph

The coloring problem of graphs in graph theory is one of the important issues and one of the hot spots, there have significant theory value and apply background. The Double-outer Planar Graph is a new special planar graph.all of the vertex appear two of the border of the planar graph,called Double-outer Planar Graph.But so far,About many problem of this special planar graph to be resolved. This paper will mainly discuss the vertex coloring problem of Double-outer Planar Graph.A k-vertex colouring of G is an assignment of k colours, 1,2,...k,to the vertices of GThe chromatic number of G is the minimum k for which G is k-colourable.On the baisis of the result of Double-outer Planar Graph, This paper considered the vertex colouring problem of the Double-outer Planar Graph. Specific to do the following work:1 .Discuss when△= 2,△= 3 ,there haveχ_v = 2 andχ_v = 3.2.When△= 4,(1)The chromatic number of G have a circle and subdivision of vertex, We get(Ⅰ)when the total vertex is 6n ,In spite of adds how many subdivision of a vertex,it isχ_v = 3.(Ⅱ) when the total vertex is 6n + 2, adds a subdivision of vertex,it isχ_v = 3, adds two or more subdivision of vertices, subdivision of vertex adds the edge of Labeling 2, it isχ_v = 3; subdivision of vertex adds the edge of Labeling 1,3, it isχ_v = 4 ;(Ⅲ) when the total vertex is 6n + 4, adds a subdivision of vertex, it isχ_n = 3, adds two or more subdivision of vertices, subdivision of vertex adds the edge of Labeling 3, it isχ_v=3; subdivision of vertex adds the edge of Labeling 1,2, it isχ_v = 4 ;(2)The chromatic number of G have a path and subdivision of vertex,We get(Ⅰ)it no add subdivision of vertex,when the total vertex is ends vertex labels of the same face is conflict,if subdivision of vertex adds the relative edge of this label,it is alsoχ_v = 4 ,adds other edges, it isχ_v = 3 .(3) The chromaticnumber of G have two paths and subdivision of vertex,We get(Ⅰ)Two paths have no subdivision of vertex,two situation isχ_v=4 ,the other situation isχ_v = 3;(Ⅱ)Twopaths adds a subdivision of vertex,it isχ_v = 3 .(4) The chromatic number of G havethree or more paths ,We get there have three colours to colour,it isχ_v = 3.3. When△= 5 , Discussed how to translate into△= 4 .