平面图的2-距离染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:lxf13098900158
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
若可以将图G画在一个平面上且使得它的边仅在顶点处相交,那么称这样的图G为平面图.本文所描述的图都是简单的,有限的平面图.图G的k-2-距离染色是指一个映射ψ:V→{1,…,k},满足若0< dG(u,v)≤2,则有ψ(u)≠ψ(v).图G的2-距离色数x2(G)=min{k|G有一个k-2-距离染色}.若给G的每一个顶点都指定可用色集L(v),|L(v)|≥k,则称L={L(v)|v∈V(G)}是G的一个的列表配置.若对于G的任何一个大小为k的列表配置L,G都是L-2-距离可染的,那么称G是k-2-距离列表可染的.G的2-距离列表色数是指使得G是k-2-距离列表可染的最小正整数k,记之为xl2(G).  平面图的2-距离染色问题,最早由Wegner在1977年发表文献并提出了得到许多数学家学者关注的猜想:对平面图G,(1)若△(G)=3,则x2(G)≤7;(2)若4≤△(G)≤7,则x2(G)≤△(G)+5;(3)若△(G)≥8,则x2(G)≤([)3/2△(G)」+1.Wegner的猜想目前为止还待研究.而对于不含短圈的平面图,能证明存在紧的2-距离色数的上界.王维凡和蔡雷镇曾提出问题:对于不含4-圈的平面图G,求满足x2(G)≤△(G)+t的t的最小值.  本论文主要研究了不含短圈的平面图的2-距离染色及2-距离列表染色.第一部分主要介绍了一些相关的概念,并综述了2-距离染色以及2-距离列表染色的研究现状和一些主要存在的问题.第二部分主要讨论围长大于等于5的平面图以及围长大于等于6的平面图的2-距离列表染色.第三部分对不含4,5-圈的平面图的2-距离列表染色数进行了讨论.第四部分主要讨论了不含4-圈的平面图的2-距离染色.
其他文献
本学位论文研究的(d,1)-全标号源于以无线电为背景的距离2标号问题.用G=(V,E)表示一个顶点集为V,边集为E的有限简单无向图.G的k-d,1)-全标号定义为从集合V(G)∪ E(G)到{0,1,…,k)的
众所周知,在微分方程定性理论中,研究极限环的稳定性、存在性、个数以及它们的分布具有非常重要的实际意义和理论价值.对于确定次数的多项式微分系统,为研究其极限环的个数,人们
本文在经典的Fisher判别分析与核函数Fisher判别分析的基础上,依据Mercer核函数理论与多分辨率分析理论,参考尺度核支持向量机的做法,把Shannon尺度函数作为核函数或核函数的一
在众多的对称化工具中,Steiner对称化无疑是既简单却又最有用的一个。尽管Jakob Steiner提出Steiner对称化的初衷在于解决等周不等式问题,其作用却马上扩展到其它领域,比如经典
生产下料广泛存在于钢铁、皮革、木料加工、玻璃切割等工业生产中,因此对原材料优化下料成为企业节约生产成本的关键技术环节。由于下料问题本身是NP难问题,不存在有效的精确
学位
本文给出了非线性互补问题NCP(F)的一个新的光滑逼近方程组,研究了光滑逼近方程组的若干性质,基此给出求解NCP(F)-步光滑化牛顿法,方法适用于F仅在IRn+上有定义的情形,算法每次迭
Clifford代数(几何代数)由William K. Clifford (1845-1879)提出,凭借其结构对几何问题的解决优势和实际价值,已经广泛应用到各个领域,如神经计算、计算机和机器人视觉、图像
在雷达、声纳、码分多址等系统的信号设计中,往往要求信号具有良好的自相关特性,这样的信号具有能将该信号与自身延迟信号区分开来的特性。因此,深入研究各种最佳离散信号,在理论
在人类科技不断发展的进程中,数字图像处理技术已广泛运用于人们的日常生活,并且被人们大量的运用在生物医学、航空航天以及目标识别和追踪等多个领域。然而,当采集图像时,通