不含4-扇的平面图的全染色

《不含4-扇的平面图的全染色》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据不含4．扇的平面图的全染色TotalColoringofPlanarGraphwithout4--fans作者：李慧慧Author：LiHuihui指导教师：王应前专业：应用数学学位：理学硕士授予单位：浙江师范大学Supervisor：!!鱼哩gYi里ggi塑Major：垒巳巳!i旦堕丛塾塾旦坐塾i璺璺MasterofScienceInstitute：．——ZhejiangNormalUniversity—．—．May,2014万方数据不含4一扇的平面图的全染色摘要设G=(vE，F)表示顶点集为

2、y，边集为E及面集为F的图．它的最大度与最小度用△与6表示．图G的一个后一全染色是一个映射咖：VUE-÷．[1，⋯，忌)，使得对任意相邻或相关联的元素U和V，满足≯(u)≠≯(u)．若G有一个尼．全染色，则说G是尼一全可染的．图G的全色数是指最小的正整数k的值．显然，全色数至少为△+1．关于图的全染色，在20世纪60年代，Vizing和Behzad就相互独立的提出：每个(简单)图G都是(△+2)．全可染的．这就是著名的全染色猜想，简称TCC．到目前为止，只有A=6的全染色猜想尚未得到解决．对于△=6平面

3、图的全色数，吴建良和王应前等分别证明不含3一圈或不含4一圈时，TCC成立．侯建锋等证明不含5．圈或6一圈时，TCC成立．最近，Roussel给出这样的结论：若平面图的最大度为6，并且图中的每一点都不同时包含‰．圈，‰∈{3，4，5，6，7，8)，则这个平面图是8一全可染的．对于平面图，多数情况下全色数是可以达到其下界(△+1)的．首先，Borodin等人证明了A≥11的平面图是(△+1)．全可染的；其次王维凡将前述结果改进到A=10，接着Kowalik等人又继续将结果改进到A=9．至于A≤8想要证明同样

4、整洁的结果似乎非常困难．考虑A=8的平面图的9一全可染性，侯建锋等人证明了A≥8且无4一圈的平面图是9一全可染的．此后，无4．圈的这个附加条件不断被减弱为：无5一圈或无6．圈；无相交l一扇；无2．扇；无3．扇等．本文在前人已有的经验基础上，主要围绕TCC，在平面图的全染色猜想中，通过研究极小反例，构建新的可约构型，运用权转移的方法证明了：(1)若G是A=6且不含4一扇的平面图，则G是8一全可染的．I万方数据(2)若G是△=8且不含4．扇的平面图，则G是9一全可染的．这里的禾扇是指交于一点的4个相继的3一

5、面，类似地，k个相继的3．面称为尼．扇．这两个结果改进了若干同类型的相关结果．关键词：平面图；全染色；扇；最大度Ⅱ万方数据T0私LCOLORlNGOFPLANARGRAPHWITHOUT4一FANSABSTRACTLetG=(KE，F)beagraphwiththesetofverticesV，thesetofedgesEandthesetoffacesF．ForaplanegraphG，weuseAand5todenoteitsmaximumdegreeandminimumdegree．Atotalk

6、-coloringofGisamapping≯：VUE一{1，⋯，尼)suchthat≯(u)≠咖(u)wheneveruand口aretwoadjacentorincidentelementsofVuE．ThetotalchromaticnumberofGistheminimumpositiveinteger七SOthatGhasak-totally-coloring．Gistotallyk-colorableifitadmitsatotalk-coloring．Clearly,thetotalchr

7、omaticnumberofGiSatleastA+1．In1960s，VizingandBehzadindependentlyconjecturedthateverysimplegraphistotally(A+2)-colorable．Thisisthefamoustotalcoloringconjecture，inshort，TCC．Sofar,theonlycasehasnotyetbeensolvedforTCCisA=6．ForplanegraphwithA=6，WuJLandWangYQe

8、tc．independentlyshowedTCCistruewhenthegraphhasnoki-cyclefor‰∈{3，4，5，6)．Recently,Rousselshowedthatifeveryvertexofaplanegraphwithmaximumdegree6ismissingfromsomek,,-cyclefork"∈{3，4，5，6，7，8)，thenthegraphistotally8-colorable．Fo