论文部分内容阅读
图G的一个正常顶点染色是指映射φ(:)V(G)→{1,2,…,k},使得任意两个相邻的点染有不同颜色.若G有一个正常k-点染色,那么就称图G是k-点可染的.图G的色数是指G有一个正常k-顶点染色的数k的最小值,用x(G)表示. 假若染色π是图G的正常顶点染色,并且对于G中任何两种颜色所导出的子图均不构成圈,那么我们称染色π是G的一个无圈染色.图G的无圈色数是指G有一个无圈k-顶点染色的数k的最小值,用xa(G)表示.若G有一个正常的无圈染色π,使得对每一个顶点v∈V,都有π(v)∈L(v),则称G是无圈L-可染的或者称π是G的一个无圈L-染色.若对满足|L(v)|≥k,v∈V的色列表L都是无圈L-可染的,那么称G是无圈k-点列表可染的或k-可选的.图G的无圈列表色数或者无圈选择数是指G是无圈k-点列表可染的数k的最小值,用xla(G)表示. 2002年,Borodin,Fon-Der Flass,Kostochka,Raspaud和Sopena证明了每个平面图是无圈7-点列表可染的,并提出了极具挑战性的猜想,即:每个平面图是无圈5-点列表可染的.此猜想目前仍未被完全解决.因此,围绕这个猜想,Montassier,Raspaud和Wang提出了另外一个猜想:每个不包含4-圈的平面图是无圈4-点列表可染的.但遗憾的是,此猜想也未完全证明. 本学位论文主要围绕以上两个猜想,着重研究了平面图的无圈点列表染色问题.本文共分三章: 在第一章中,我们介绍了本文所涉及的有关概念,并简述了无圈点列表染色的研究现状. 在第二章中,我们证明了:不含相邻的4-圈和i-圈的平面图是无圈6-点列表可染的,其中i∈{3,4,5,6}. 在第三章中,我们证明了以下两个结果: (1)不含4-圈,相邻5-圈,相邻的3-圈和6-圈的平面图是无圈4-点列表可染的. (2)若平面图G中的i-圈和j-圈的距离至少为1,其中3≤i,j≤5,则G是无圈4-点列表可染的.