图的点荫度和列表点荫度

论文摘要

图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.

论文目录

文章来源

类型: 硕士论文

作者: 凌银

导师: 黄丹君

关键词: 列表点荫度,点荫度,森林染色,环面图,平面图

来源: 浙江师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 浙江师范大学

分类号: O157.5

DOI: 10.27464/d.cnki.gzsfu.2019.000811

总页数: 63

文件大小: 2667K

下载量: 29

相关论文文献

• [1].不含相交5-圈的平面图的线性2-荫度[J]. 山东大学学报(理学版) 2020(07)
• [2].不含相交4-圈的平面图的线性2-荫度[J]. 应用技术学报 2017(02)
• [3].关于图的全荫度和列表全荫度的一些结果（英文）[J]. 南京大学学报(数学半年刊) 2017(01)
• [4].可平面图的线性2-荫度的新上限（英文）[J]. 数学进展 2016(02)
• [5].嵌入曲面的图的点荫度[J]. 山东大学学报(理学版) 2015(02)
• [6].关于曲面的列表点荫度定义与探讨[J]. 塔里木大学学报 2010(01)
• [7].平面图线性2-荫度的一个上界[J]. 山东大学学报(理学版) 2014(04)
• [8].不含弦5-圈和弦6-圈的平面图的线性2-荫度[J]. 山东大学学报(理学版) 2014(06)
• [9].播种密度及遮荫度对草珊瑚幼苗生长的影响[J]. 福建林业科技 2013(01)
• [10].不含4-圈和5-圈的平面图的线性2-荫度[J]. 山东大学学报(理学版) 2012(06)
• [11].不含相邻三角形的平面图的线性2-荫度[J]. 浙江师范大学学报(自然科学版) 2011(02)
• [12].某些不含5-圈的图的线性2-荫度[J]. 科技信息 2011(29)
• [13].最大平均度不超过4的图的线性2-荫度[J]. 山东大学学报(理学版) 2018(06)
• [14].不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界[J]. 运筹学学报 2019(01)
• [15].不含3-圈和4-圈的平面图的线性2-荫度[J]. 河南工程学院学报(自然科学版) 2011(02)
• [16].超图的无圈分解问题[J]. 周口师范学院学报 2008(05)
• [17].平面图点荫度的一个局部条件[J]. 数学进展 2020(02)
• [18].遮荫对草地早熟禾生长的影响[J]. 内蒙古民族大学学报(自然科学版) 2012(03)
• [19].一类整数距离图的点荫度[J]. 天津师范大学学报(自然科学版) 2012(03)
• [20].平面图的各种染色综述[J]. 广州大学学报(自然科学版) 2019(05)
• [21].4-圈不共点的平面图的线性2-荫度[J]. 山东大学学报(理学版) 2017(12)
• [22].外1-平面图的均匀点荫度[J]. 计算机工程与应用 2018(10)
• [23].均衡完全三部图K_(3(n))的线性3-荫度[J]. 天津师范大学学报(自然科学版) 2012(02)
• [24].Halin图的线性k-点荫度[J]. 数学进展 2020(04)
• [25].K_4-minor-free图的线性2-荫度[J]. 运筹学学报 2008(04)
• [26].整数距离图G(D_(m,k,2))的点荫度[J]. 数学物理学报 2010(04)
• [27].兰花夏秋如何养护[J]. 农家之友 2018(08)
• [28].遮荫对观赏草丽色画眉生长、光合以及生物量的影响[J]. 草地学报 2013(05)
• [29].不同遮荫度对南方红豆杉幼树生长量的影响试验[J]. 林业调查规划 2014(06)
• [30].遮荫处理下两种园林植物叶绿素含量及荧光参数的研究[J]. 甘肃科技 2009(03)

标签：列表点荫度论文;  点荫度论文;  森林染色论文;  环面图论文;  平面图论文;