论文部分内容阅读
设G=(V, E,F)表示顶点集为V,边集为E及面集为F的图.它的最大度与最小度用△与δ表示.图G的一个k-全染色是一个映射φ:V∪E→{1,…,k},使得对任意相邻或相关联的元素u和v,满足φ(u)≠φ(v).若G有一个k-全染色,则说G是k-全可染的.图G的全色数是指最小的正整数k的值.显然,全色数至少为△+1. 关于图的全染色,在20世纪60年代,Vizing和Behzad就相互独立的提出:每个(简单)图G都是(△+2)-全可染的.这就是著名的全染色猜想,简称TCC.到目前为止,只有△=6的全染色猜想尚未得到解决.对于△=6平面图的全色数,吴建良和王应前等分别证明不含3-圈或不含4-圈时,TCC成立.侯建锋等证明不含5-圈或6-圈时,TCC成立.最近,Roussel给出这样的结论:若平面图的最大度为6,并且图中的每一点都不同时包含kv-圈,kv∈{3,4,5,6,7,8},则这个平面图是8-全可染的. 对于平面图,多数情况下全色数是可以达到其下界(△+1)的.首先,Borodin等人证明了△≥11的平面图是(△+1)-全可染的;其次王维凡将前述结果改进到△=10,接着Kowalik等人又继续将结果改进到△=9.至于△≤8想要证明同样整洁的结果似乎非常困难.考虑△=8的平面图的9-全可染性,侯建锋等人证明了△≥8且无4-圈的平面图是9-全可染的.此后,无4-圈的这个附加条件不断被减弱为:无5-圈或无6-圈;无相交1-扇;无2-扇;无3-扇等. 本文在前人已有的经验基础上,主要围绕TCC,在平面图的全染色猜想中,通过研究极小反例,构建新的可约构型,运用权转移的方法证明了: (1)若G是△=6且不含4-扇的平面图,则G是8-全可染的. (2)若G是△=8且不含4-扇的平面图,则G是9-全可染的. 这里的4-扇是指交于一点的4个相继的3-面,类似地,k个相继的3-面称为k-扇.这两个结果改进了若干同类型的相关结果.