平面图的无圈点列表染色

发布时间：2020-05-09 00:23

【摘要】：令G是一个有限简单平面图.用V(G)和E(G)分别表示图G的顶点集和边集,简记为V和E.若存在一个映射π:V → {1,2,…,k}满足对(?)xy∈E,都有π(x)≠ π(y),则称π是图G的一个正常k-点染色,并称G是k-点可染的.图G的点色数x(G)是使得G是k-点可染的最小正整数k的值.若G存在一种正常点染色,满足不存在二色圈,则称这种点染色是无圈的.也就是说,每个圈至少使用三种颜色.图G的无圈点色数,记作xa(G),是使得G有一个无圈k-点染色的最小正整数k的值.著名数学家Grunbaum教授于1973年最早提出图的无圈点染色的概念,他证明了每个平面图是无圈9-点可染的,同时猜想:每个平面图是无圈5-点可染的,该猜想后被Borodin证明.给图G中的每一个顶点v配置一个颜色集合L(v),记L={L(v)|v∈V},如果存在一种染色π,其中π(v)∈L(v),使得π是正常点染色,那么称G是L-点可染的或称G有一个L-点染色.若对所有的v ∈ V(G),配置任意的列表L,其中|L(v)|=k,使得G是L-点可染的,则称G是k-点列表可染的.我们把使得G是k-点列表可染的最小正整数k的值称为G的点列表色数,记作xl(G).若存在一个无圈点染色π,使得对每个点v都有π(v)∈L(v),则称G是无圈L-点可染的.同时染色π被称作G的一个无圈L-点染色.类似地,当|L(v)| = k且G是无圈L-点可染的,称G是无圈k-点列表可染的.G的无圈点列表色数是使得G是无圈k-点列表可染的最小正整数k-的值,记作xal(G).2002 年,Borodin,Fon-Der Flaass,Kostochka,Raspaud 和 Sopena 首次提出并研究了平面图的无圈点列表染色问题.他们证明了每个平面图是无圈7-点列表可染的,并且提出了极具挑战性的猜想:每个平面图是无圈5-点列表可染的.而后,在2006年,Montassier,Raspaud和Wang进而提出了猜想:每个不包含4-圈的平面图是无圈4-点列表可染的.这两个猜想至今仍悬而未决.近年来,平面图的无圈4-点列表染色问题引起了国内外研究者的极大关注.本学位论文主要围绕此问题展开研究.我们将给出平面图为无圈4-点列表可染的新的充分条件.论文框架结构及内容如下:在第一章中,我们先给出本文将用到的基本概念,再简述相关领域的研究现状和本文的研究结果.在第二章,第三章和第四章中,我们均使用反证法,通过构造极小反例,运用色延拓技巧以及经典的权转移方法,分别证明了以下三个结果:(1)每个不包含相交5--圈的平面图是无圈4-点列表可染的.(2)每个既不包含4-圈,也不包含相交3-圈和相交5-圈的平面图是无圈4-点列表可染的.(3)每个不包含4-,7-和9-圈的平面图是无圈4-点列表可染的.
【图文】：

平面图的无圈点列表染色

图３．１：引理３．７中两种可能会发生的情况．逡逑
【学位授予单位】：浙江师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】