论文部分内容阅读
用V，E，F，△和δ分别表示平面图G的顶点集，边集，面集，最大度和最小度.若V∪ E中的元素能用k种颜色进行染色，使得任意两个相邻或相关联的元素染有不同的颜色，则称G是k-全可染的.G的全色数χT(G)=min{k｜G是k-全可染的}。显然，给每一个图进行全染色至少要用△+1个色，即χT(G)≥△+1.
关于图的全染色问题，早在20世纪60年代，Vizing和Behzad分别提出猜想：对任意图G，χT(G)≤△+2.这一猜想被后人称为全染色猜想(Total ColoringConjecture)，简记为TCC.随着研究的深入，人们发现很多图类G不仅满足TCC，而且它们的全色数还能取到相应的下界，也就是说χT(G)=△+1.到目前为止，已经证明对于△≥g的平面图G，χT(G)=△+1.但对于4≤△≤8的平面图，人们还未找到非(△+1)-全可染的例子.于是自然猜想：对于△≥4的平面图G，χT(G)=△+1是否也成立?TCC是对任意图的全色数进行猜想，这里是对平面图的全色数进行猜想，于是我们把这个猜想称作平面图的全染色猜想(TotalColoring Conjecture for Plane Graphs)，简称为PTCC.
本文围绕著名的全染色猜想(TCC)和平面图全染色猜想(PTCC)，主要研究平面图G的全色数χT(G).运用Discharging方法主要证明了
(1)若G是△=6且不含4-圈的平面图，则χT(G)=7；
(2)若G是△=7且不含5-圈的平面图，则χT(G)=8；
(3)若G是△=8且不含带弦的5-圈的平面图，则χT(G)=9；
(4)若G是△=8且不含带弦的6-圈的平面图，则χT(G)=9；
(5)若G是△=8且不含相交三角形的平面图，则χT(G)=9；
(6)若G是△=8且不含相邻三角形的平面图，则χT(G)=9.