论文部分内容阅读
图论这门学科最早起源于著名的哥尼斯堡七桥问题,而对图进行染色的研究则起源于著名的四色问题,即对平面上的任何一张地图,总可以用至少四种颜色对每个国家进行染色,且使得相邻的国家染有不同的颜色.图的染色问题一般可分为:顶点染色,边染色,全染色,边面染色和完备染色等等.本学位论文研究的是平面图的全染色,并得出了三个主要结果.
给定一个平面图G=(V,E),分别用V,E,F,△和δ表示它的顶点集,边集,面集,最大度和最小度.平面图的全染色就是对平面图的顶点集和边集中的元素进行染色,如果能用k种颜色使得任意两个相邻或相关联的元素染有不同的颜色,则称图G有一个正常的k-全染色,也称图G是k-全可染的.图G的全色数就是使得图G是正常k-全染色的最小的正整数k.显然,给平面图进行正常全染色至少要用△+1种颜色.
对于图的全染色,早在20世纪60年代,Vizing和Behzad就分别独立的提出了全染色猜想:任意的简单图G都是△+2-全可染的.到目前为止,只有最大度为6是否是8-全可染的问题尚未得到解决.本学位论文在最大度为6的基础上加一些限制条件得出了以下结果:
(1)设图G是最大度为6且不含相邻4-圈的平面图,则G是8-全可染的.
在对全染色的研究过程中,人们有意思的发现很多图类的全染色数还能取到相应的下界,即xT(G)=△+1.于是人们很自然的猜想:对任意的平面图G,xT(G)=△+1.因为这里是对平面图的全色数进行的猜想,于是就把这个猜想称为平面图的全染色猜想(Total Coloring Conjecture for Plane Graphs),简称PTCC.到目前为止,△≥9的平面图G,已被证实PTCC成立.前面的师兄师姐们对最大度为8和最大度为7的平面图再加一些限制条件,证明PTCC成立已经得出了很多有意义的结果.本学位论文主要研究的是最大度为6的平面图的PTCC问题,得出了以下两个结果:
(2)设图G是最大度为6且不含5-圈和相邻4-圈的平面图,则G是7-全可染的;
(3)设图G是最大度至少为6且不含相邻4--圈的平面图,则G是(△+1)-全可染的.