平面图的无圈点列表染色

《平面图的无圈点列表染色》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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