图的列表点荫度

发布时间：2017-10-06 07:32

  本文关键词：图的列表点荫度

  更多相关文章： 列表点荫度 点荫度 森林染色 环面图

【摘要】：图G的点荫度是G的顶点集V(G)的最小划分数,使得每个点划分集的导出子图是一个森林.图G的一个k-森林染色是指一个映射Φ：V(G)→{1,2…,k},使得每一个点导出子图G[K]是一个森林,其中Vi是颜色为i的顶点集.G的点荫度是指G有一个k-森林染色的数k的最小值,用a(G)表示.若G有一个森林染色π,使得对每个顶点v都有π(w) ∈ L(v),那么就称G是L-森林可染的.若对于任意列表|L(x)|≥k,G是L-森林可染的,那么就称G是k-列表森林可染的.G的列表点荫度是指G是k-列表森林可染的数k的最小值,用a_l(G)表示.点荫度最早是由Chartrand, Kronk和Wa_ll于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-圈不相邻的平面图,则a_l(G)≤2.那么,对于环面图而言,上述结果是否仍成立呢?本学位论文主要研究了平面图和环面图的列表点荫度问题,共分三章.在第一章中,我们介绍了基本概念和相关领域的研究现状,并且呈现了本文的主要结果.在第二章中,我们研究了环面图的列表点荫度,证明了下面三个结果：(1)若G是3-圈与5-圈不相邻的环面图,则a_l(G)≤2.(2)若G是4-圈与5-圈不相邻的环面图,则a_l(G)≤2.(3)若G是3-圈与4-圈不相邻的环面图,则a_l(G)≤2.在第三章中,我们研究了平面图的列表点荫度,证明了：若G是不含相交5-圈的平面图,则a_l(G)≤2.
【关键词】：列表点荫度 点荫度 森林染色 环面图
【学位授予单位】：浙江师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要3-4
• Abstract4-8
• 第一章 绪论8-14
• 1.1 基本概念8-9
• 1.2 点荫度与列表点荫度的研究概况9-13
• 1.3 本文主要结果13-14
• 第二章 环面图的列表点荫度14-50
• 2.1 一些记号14
• 2.2 3-圈与5-圈不相邻的环面图的列表点荫度14-21
• 2.3 3-圈与4-圈不相邻的环面图的列表点荫度21-33
• 2.4 4-圈与5-圈不相邻的环面图的列表点荫度33-50
• 2.4.1 结构引理34-44
• 2.4.2 主要结论及证明44-50
• 第三章 平面图的列表点荫度50-60
• 3.1 结构性质50-52
• 3.2 定理3.1的证明52-60
• 参考文献60-62
• 攻读学位期间取得的研究成果62-64
• 致谢64-66

【相似文献】

中国期刊全文数据库 前10条

1 吴建良;Halin图的一些路分解[J];山东矿业学院学报;1998年01期

2 杨爱民;线图的荫度[J];山西大学学报(自然科学版);1998年01期

3 魏二玲,刘彦佩,杨爱民,康利;乘积图的荫度[J];北方交通大学学报;2000年02期

4 薛妮妮;严志丹;;关于曲面的列表点荫度定义与探讨[J];塔里木大学学报;2010年01期

5 王雪梅;李会序;;某些不含5-圈的图的线性2-荫度[J];科技信息;2011年29期

6 张忠辅;王建方;;荫度与团覆盖数的关系[J];兰州铁道学院学报;1991年01期

7 张忠辅;王建方;;关于图的点荫度[J];应用数学;1991年02期

8 张建州;;图的点星荫度[J];电子科技大学学报;1992年01期

9 熊黎明,文莉莉;图的点线荫度(英文)[J];江西师范大学学报(自然科学版);1994年02期

10 黄荷姣,魏暹荪,张江涛;有限图的边荫度分解[J];陕西师范大学学报(自然科学版);1998年04期

中国博士学位论文全文数据库 前2条

1 左连翠;图的点荫度和点线性荫度[D];山东大学;2005年

2 杨爱峰;图的广义着色[D];郑州大学;2004年

中国硕士学位论文全文数据库 前10条

1 金政国;平方图的点荫度[D];北京交通大学;2010年

2 姚梅;圈限制条件下平面图的线性2-荫度[D];河北工业大学;2015年

3 赵宗正;短圈不相交的平面图的线性2-荫度[D];河北工业大学;2015年

4 郭志伟;图的强平衡顶点荫度若干问题研究[D];青海师范大学;2016年

5 黄莉;图的列表点荫度[D];浙江师范大学;2016年

6 薛妮妮;图的列表点荫度[D];新疆大学;2008年

7 石淼;k-退化图的M图的点荫度[D];北京交通大学;2010年

8 王苒群;几类图的线性k-荫度[D];天津师范大学;2013年

9 马刚;平方图的点荫度[D];山东大学;2007年

10 陶金颖;不含弦5-圈和弦6-圈的平面图的线性2-荫度[D];河北工业大学;2014年

，

本文编号：981517