平面图的Injective染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:hello_junz
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文研究对象限于简单有限图,对于图G的一个正常顶点k-染色,指的是从G的顶点集合V(G)到颜色集合{1,2,…,k}的一个映射c.使得距离为1的点染的颜色也不同,我们用x(G)来表示满足上述要求的最小的正整数尼,称之为图G的色数;若图G的一个顶点染色φ称为Injective染色,那么图G中有公共邻点的两个顶点染不同的颜色.类似地,xi(G)称为图G的Injective色数,用xli(G)来表示Injective列表色数.对图G的Injective色数显然有△(G)≤xi(G)≤△(G)(△(G)-1)+1,(G≠K2),并且xi(G)≥x(G).  自Hahn等人提出了Injective染色的概念以来,Injective染色的研究热度始终不减,并成为图的染色理论中重要的研究方向.总结起来,人们主要研究了在图的围长、最大度、以及最大平均度等的条件限制下的Injective色数.当然,前人提出的许多重大猜想至今仍然是许多海内外学者投身科研的热情因素之一,其中就包括著名的四色定理.  在本文中,主要讨论了在不含短圈的条件限制下,平面图G的Injective色数.第一部分介绍了Injective染色的相关背景以及研究现状.作为相对比较新的平面图染色研究方向,我们做的主要工作是研究了平面图的Injective染色数在围长至少为5时的最优值.在后面的章节里面详细讨论了Injective染色数为△+4的充分条件.
其他文献
物理学和工程学中,许多问题的数学模型即为一散逸的动力系统。这些系统的特点是拥有一有界的吸引集,即从任意的初始条件出发的解经过一定时间后进入并随后始终保持在这个吸引集
图的染色问题是图论研究中一个活跃的领域,因此各类染色问题被相继提出并加以发展应用,赖宏建等人在2006年提出了条件染色.图的标号问题就是图的染色问题的推广,其理论研究背景是
近年来,Poisson代数得到很多不同形式的推广,如微分分次Poisson代数.本文是在此基础上讨论了n次微分分次Poisson代数相关性质,主要内容如下:  第一部分介绍了本文的研究目的,主
图像修复一直以来都是图像处理领域一个很受关注的问题,而且也是进一步图像处理应用的预处理过程.主要是利用一定的算法针对产生划痕和有缺损的图像进行修复,或者从图像中去除
本文主要研究了基于分数布朗运动的Wick型积分的随机微分方程解的存在唯一性和P阶矩估计。   2000年,T.E.Duncan等人(见[62])给出了分数布朗运动Wick型积分的It(o)公式,本文在此