论文部分内容阅读
图G的点荫度va(G)是指G的顶点集V(G)的最小划分数,使得每一个划分集的点导出子图是一个森林.图G的k-森林染色指存在一个映射φ:V(G)→{1,2,…,k},使得任何一个点导出的子图G[Vi]是一个森林,其中Vi是指颜色为i的顶点所组成的集合.图G的点荫度亦指G有k;-森林染色的数fk的最小值.设L是V(G)的一个列表配置.若图G有一个森林染色φ,使得对每个顶点v都有φ(v)∈L(v),则称图G是L-森林可染的.若对于任意列表|L(v)|≥ k;,图G都是L·森林可染的,则称图G是k-列表森林可染的.图G的列表点荫度是指G是fk-列表森林可染的数k的最小值,用valist(G)表示.1968年,Chartrand,Kronk和Wall提出了点荫度的概念.同时,他们证明了对任意图G,有va(G)≤[△+1/2];并且若G是平面图,则va(G)≤ 3.2008年,Raspaud和Wang证明了:若图G是不含k-圈,k ∈{3,4,5,6},的平面图,则va(G)≤ 2.同时,他们提出是否存在最大的正整数μ,使得对任意的k;∈{3,4,5,...,μ},若G是不含k-圈的平面图,则va(G)≤2?2012年,Huang,Shiu和Wang证明了若图G是不含7-圈的平面图,则va(G)≤2.同年,Chen,Raspaud 和Wang 解决了Raspaud 和Wang 于2008年提出的猜想:若G是不含相交三角形的平面图,则va(G)≤2.那么,若G是不含相交k-圈的平面图,k∈{4,5,6,7},是否有va(G)≤2?2018年,Cai,Wu和Sun证明了若G是不含相交5-圈的平面图,则va(G)≤2.2009年,Borodin和Ivanova证明了:若G是3-圈与4-圈不相邻的平面图,则valist(G)≤2.那么,对于环面图而言,上述结果是否任然成立呢?2016年,Chen,Huang和Wang证明了,若G是3-圈与4-圈不相邻的环面图,则valist≤2.2014年,Zhang证明了,若G是不含5-圈的环面图,则valist(G)≤2.2015年,Huang,Chen和Wang证明了,若G是3-圈和5-圈不相邻的环面图,则valist(G)≤2.2016年,Zhang证明了,若G是环面图,且既不含7-圈也不含相邻的三角化4-圈,则va(G)<2.结合前人的研究成果,本学位论文主要研究两类特殊的图(平面图和环面图)的点荫度与列表点荫度问题,共分为三章.第一章,介绍了研究过程中用到的基本概念以及点荫度与列表点荫度的研究现状,同时给出了本文主要结果.第二章,研究了与平面图相关的点荫度问题,主要得到了下面两个结果.(1)若G是3-圈与6-圈不相邻的平面图,则va(G)≤2.(2)若G是平面图,且G中的任何一个点都不同时与3-,4-,5-,6-圈关联,则ua(G)≤2.第三章,研究了环面图的列表点荫度,得到了若G是5-圈不同时和3-圈与4-圈相邻的环面图,则valist(G)≤2.