论文部分内容阅读
图G的点荫度是G的顶点集V(G)的最小划分数，使得每个点划分集的导出子图是一个森林.图G的一个k-森林染色是指一个映射φ:V(G)→{1，2，…，k}，使得每一个点导出子图G[Vi]是一个森林，其中Vi是颜色为i的顶点集.G的点荫度是指G有一个k-森林染色的数k的最小值，用a(G)表示. 若G有一个森林染色π，使得对每个顶点v都有π(v)∈L(v)，那么就称G是L-森林可染的.若对于任意列表|L(x)|≥k，G是L-森林可染的，那么就称G是k-列表森林可染的.G的列表点荫度是指G是k-列表森林可染的数k的最小值，用al(G)表示. 点荫度最早是由Chartrand，Kronk和Wall于1968年提出的.同时，他们证明了对任何图G，有a(G)≤[△+1/2];且若G是平面图，则a(G)≤3.后来，Raspaud和Wang(2008)，Huang，Shiu和Wang(2012)证明了:若G是不含k-圈，k∈{3，4，5，6，7}，的平面图，则a(G)≤2.2012年，Chen，Raspaud和Wang解决了Raspaud和Wang(2008)提出的猜想:若G是不含相交三角形的平面图，则a(G)≤2.那么，若G是不含相交k-圈的平面图，k∈{4，5，6，7}，是否有a(G）≤2呢？ Borodin和Ivanova证明了:若G是3-圈与4-圈不相邻的平面图，则al(G)≤2.那么，对于环面图而言，上述结果是否仍成立呢？ 本学位论文主要研究了平面图和环面图的列表点荫度问题，共分三章. 在第一章中，我们介绍了基本概念和相关领域的研究现状，并且呈现了本文的主要结果. 在第二章中，我们研究了环面图的列表点荫度，证明了下面三个结果: (1)若G是3-圈与5-圈不相邻的环面图，则al(G)≤2. (2)若G是4-圈与5-圈不相邻的环面图，则al(G)≤2. (3)若G是3-圈与4-圈不相邻的环面图，则alG)≤2. 在第三章中，我们研究了平面图的列表点荫度，证明了:若G是不含相交5-圈的平面图，则al(G)≤2.