欢迎来到天天文库
浏览记录
ID:33518832
大小:1.15 MB
页数:44页
时间:2019-02-26
《不含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
此文档下载收益归作者所有