双外平面图的点染色

The Vertex coloring of the double outer planar graph

图染色问题是图论研究中的重要问题之一,本文针对双外平面图G的点色数进行研究,并证明了:(1)不加剖分点时,当顶点数为6n+k(n=1,2,...)(k=1,2,3)时,χv=4;否则χv=3.(2)χv=4时,当在相同面上两端的顶点标号冲突时,若剖分点加在这个标号相对的边上时,仍然有χv=4;否则χv=3.

The graph coloring problem is one of the important problems of graph theory. The article studies the double outer pla- nar graph G of chromatic number, and proved（ 1 ） Without cut points, when the number of vertices is 6n ＋ k（ n = 1,2,... ） （ k = 1,2,3 ）, Xv = 4 ;or xv = 3. （2）xv = 4when the vertex labeling conflict at the ends of the same surface, if the cut points on this label relative at the edge, there are still XV = 4;or XV = 4.