欢迎来到天天文库
浏览记录
ID:36788580
大小:1.80 MB
页数:60页
时间:2019-05-15
《平面图的无圈点列表染色》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、平面图的无圈点列表染色AcyclicChoosabilityofPlanarGraphs作者:张舸Author:圣坠塑g堡竺指导教师:王维凡专业:应用数学Supervisor:盟塑g坠i墅Major:AppliedMathematics一●____●-__●_____-__-_-_●__________-______●-●●●_---_●。___●-_-___●______●_____________。__-一学位:理堂耍圭Degree:授予单位:浙江师范大学MasterofScienceInstitute:...
2、...Z————h————e——jiangNormalUniversity..—May,2013摘要l呲吣2吣4吣1吣吣4帆3咖5帆6础图G的一个正常顶点染色是指映射咖:v(c)一{1:2,⋯:七}:使得任意两个相邻的点染有不同颜色.若G有一个正常缸点染色,那么就称图G是七一点可染的.图G的色数是指G有一个正常舡顶点染色的数七的最小值,用x(C)表示.假若染色7r是图G的正常顶点染色,并且对于G中任何两种颜色所导出的子图均不构成圈,那么我们称染色7r是G的一个无圈染色.图G的无圈色数是指G有一个无圈缸顶点染色的数七
3、的最小值,用xn(G)表示.若G有一个正常的无圈染色7r,使得对每一个顶点t,∈V,都有7r(1,)∈三(t,),则称G是无圈厶可染的或者称7r是G的一个无圈L染色.若对满足IL(”)I≥七,V∈V的色列表L都是无圈L可染的,那么称G是无圈七一点列表可染的或b可选的.图G的无圈列表色数或者无圈选择数是指G是无圈“点列表可染的数k的最小值,用x:(G)表示.2002年,Borodin,Fon-DerFlass,Kostochlm,Raspaud和Sopena证明了每个平面图是无圈7-点列表可染的:并提出了极具挑战性的
4、猜想,aP=每个平面图是无圈5一点列表可染的.此猜想目前仍未被完全解决.因此,围绕这个猜想,Montassier,Raspaud和Wang提出了另外一个猜想:每个不包含垂圈的平面图是无圈垂点列表可染的.但遗憾的是,此猜想也未完全证明.本学位论文主要围绕以上两个猜想,着重研究了平面图的无圈点列表染色问题.本文共分三章:在第一章中:我们介绍了本文所涉及的有关概念,并简述了无圈点列表染色的研究现状.在第二章中,我们证明了:不含相邻的垂圈和i一圈的平面图是无圈6-点列表可染的,其中i∈{3,4,5,6).在第三章中,我们证
5、明了以下两个结果:(1)不含垂圈:相邻5-圈,相邻的3-圈和6.圈的平面图是无圈缸点列表可染的.(2)若平面图G中的i一圈和歹一圈的距离至少为1,其中3≤i,J≤5,则G是无圈缸点列表可染的.关键词:圈;无圈染色;无圈列表染色;平面图AbstractAproperk-coloringofagraphGisamapping≯:v(a)-÷{1,2,⋯,忌),suchthatno础acentverticesreceivessamecolors.IfGhasaproperk-coloring.thenGissaidtob
6、ek-colorable.Thechromaticnumber,denotedbyx(G),istheleastnon-negativeinteger七suchthatGisk—colorable.Acoloring丌isacyclicif7risapropervertexcoloringofGsuchthatanycyclesubgraphhasatleast3colors,Theacy.clicchromaticnumber,denotedbyXa(G),istheleastnon-negativeintege
7、rksuchthatGisacyclick-coloring.AgraphGisacyclicallyL-listcolorableifforagivenlistassignmentL={£(口):u∈y),thereexistsaproperacycliccoloring7rofGsuchthat7r(口)∈L(v)forall口∈V.IfGisacyclicallyL-listcolorableforanylistassignmentwithI£(")I≥kforallV∈V,thenGisacyclicall
8、yk—choosable.Theacycliclistchromaticnumber,denotedbyx:(G),istheleastnon-negativeintegerksuchthatGisacyclick-choosable.In2002,Borodin,Fon—DerFlass,Kostochka,RaspaudandSopenaprovedth
此文档下载收益归作者所有