围长至少为5的平面图的injective染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:msbt098
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文研究的图类仅限于有限简单图.图G的一个injectivek-染色是指映射c:V(G)→{1,2,…,k},使得有公共邻点的2个顶点u,v满足c(u)≠c(v).若图G有一个injectivek-染色,则称图G是injectivek-可染的,并称xi(G)=min{k|G是injective k-可染的}为图G的injective色数.显然,图的injective染色未必是正常顶点染色.易知,图G的injective色数满足△(G)≤xi(G)≤△(G)(△(G)-1)+1,并且当G≠K2时,xi(G)≥x(G).  自Hahn等人在2002年提出了injective染色的概念后,injective染色的相关研究成为了图染色理论中重要的研究方向之一.它与图的L(0,1)-标号以及平方图染色的联系很是紧密.目前,人们主要是基于图的围长、最大度或者最大平均度等的限制条件下研究其injective色数,或者研究图的injective色数的算法复杂性.  本文探讨了不含部分短圈的平面图G的injective色数.第一部分介绍了injective染色的基本概念、述语、研究近况及存在的问题.第二部分介绍了围长至少为5的平面图,其injective色数为△+3的充分条件.第三部分介绍了injective染色的一些可研究问题.
其他文献
设f是一个映射,它给G的每个点u分配一个含有b个颜色的颜色集合f(v),那么称f为图G的一个b-重染色.给定图G的一个b-重染色f,点v相对于f的总缺憾定义为deff(v)=∑u∈N(v)|f(u)∩f(v
学位
概念格作为形式概念分析的核心数据结构,已经成为一种用于数据组织和分析的形式化工具。在概念格的应用中,首先要根据形式背景建立相应的概念格,因此高效的建格算法是概念格有效
在人工智能系统、人工神经网络之后,又出现了一个令人瞩目的学科,它就是进化计算。它很好的模拟了达尔文提出的生物进化和遗传的过程。进化计算依照“适者生存”的原则,通过一组
Toeplitz方程组的求解问题是计算数学研究的一大热门,它在自动控制、数字信号处理、图像存储等众多科学领域中广泛应用.近年来,国内外学者都在寻找一种运算量小、存储量小、
对流扩散方程初值问题是近年来初值问题的主要研究课题之一,连续系数对流扩散方程的相关问题得到了较好的处理,其成果也为可变系数及间断系数的对流扩散方程初值的研究提供了