双外平面图的点染色

刘广德

(枣庄学院 数学与统计学院，山东 枣庄 277160)

0 基本定义

定义1:如果一个图是可嵌入平面的，且它所有顶点出现在无穷面的边界上，称该图为外平面图.无穷面称为外面，其余面称为内面［1］.

定义2:所有点出现在两个面的边界上的平面图，称为双外平面图，我们把这两个面称为外面［2］.

1 主要定理

定理1 双外平面图中只有一条路时:当顶点数为6n+k(n=1，2，...)(k=1，2，3)时，χv=4，否则 χv=3［3，4］.

证明 对于一条路从右向左按照1.2.3进行标号，如图1所示:

图1 8种结构Fig.1 The 8 kinds of structure

继续往下画时，第9种结构和图1中的第3种一样了，从上边的8种结构来看第1、2、3、4、5这5种结构都可以用3种颜色来染色，第6、7、8这3种结构都要用4种颜色来染色，第9种和第3种，第10种和第4种，第11种和第5种，第12种和第6种…都可以用一样的颜色来染色，第6、7、8这3种结构对应的顶点数为7、8、9.

由此可以得出当顶点数为6n+k(n=1，2，...)(k=1，2，3)时，χv=4，否则χv=3.证毕.

定理2:在双外平面图中只有一条路，且χv=4时，当在相同面上两端的顶点标号冲突时，如果剖分点加在这个标号相对的边上时，仍然有 χv=4，否则 χv=3［5－6］.

证明:(1)对于图1中的第6种结构加入1个剖分点有如下图2的情况.当我们可以重新进行进行标号，有的可以用3种颜色进行染色，结果如图3所示

其中有2种情况加入1个剖分点后仍然需要4种颜色来染，这2种情况都是剖分点加在标号为1的点对应的边上，因为在相同面上1的标号冲突.

(2)对于图1中的第7种结构加入1个剖分点有如图4的情况.我们可以重新进行进行标号，有的可以用3种颜色进行染色，结果如图5所示:

其中有6种情况加入1个剖分点后仍然需要4种颜色来染，这6种情况都是剖分点加在标号为1和2的点对应的边上，因为在相同面上1和2的标号都冲突.

(3)对于图1中的第8种结构加入1个剖分点有如图6情况.我们可以重新进行进行标号，有的可以用3种颜色进行染色，结果如图7所示:

其中有4种情况加入1个剖分点后仍然需要4种颜色来染，这4种情况都是剖分点加在标号为2的点对应的边上，因为在相同面上2的标号都冲突.

2 结论

由上边的3种χv=4加一个剖分点的结果，有以下结论:当在相同面上两端的顶点标号冲突时，如果剖分点加在这个标号相对的边上时，仍然有χv=4，加在其他边上时，有χv=3.另在第8种结构时，当剖分点加在相同面上两端的顶点标号不冲突的边上，仍然有χv=4.证毕.

［1］JA，默帝 USR.图论及其应用［M］.北京:科学出版社，1984.

［2］孔立.一个特殊双外平面图的全染色［J］.洛阳大学学报.2005，20(2):7－9.

［3］陈东灵，吴建良.外平面图的一个结构定理［J］.山东科技大学学报.1999，18(4):41－43.

［4］张苏梅.外平面图的 L(d，1)－标号［J］.济南大学学报(自然科学版).2006，20(3):258－260.

［5］孔立.双外平面图的全染色［J］.山东轻工业学院学报.2005，19(2):81－84.

［6］孔立.双外平面图的边面染色［J］.烟台师范学院学报(自然科学版).2005，21(2):106－108.