平面图的injective染色

发布时间：2017-11-23 21:09

  本文关键词：平面图的injective染色

  更多相关文章： Injective染色 平面图 围长 最大度 最大平均度

【摘要】：本文研究对象限于简单有限图,对于图G的一个正常顶点k-染色,指的是从G的顶点集合V(G)到颜色集合{1,2,…,k｝的一个映射c.使得距离为1的点染的颜色也不同,我们用X(G)来表示满足上述要求的最小的正整数k,称之为图G的色数；若图G的一个顶点染色Φ称为Injective染色,那么图G中有公共邻点的两个顶点染不同的颜色.类似地,Xi(G)称为图G的Injective色数,用Xil(G)来表示Injective列表色数.对图G的Injective色数显然有△(G)≤χi(G)≤△(G)(△(G)-1)+1,(G≠K2),并且χi(G)≥χ(G).自Hahn等人提出了Injective染色的概念以来,Injective染色的研究热度始终不减,并成为图的染色理论中重要的研究方向.总结起来,人们主要研究了在图的围长、最大度、以及最大平均度等的条件限制下的Injective色数.当然,前人提出的许多重大猜想至今仍然是许多海内外学者投身科研的热情因素之一,其中就包括著名的四色定理.在本文中,主要讨论了在不含短圈的条件限制下,平面图G的Injective色数.第一部分介绍了Injective染色的相关背景以及研究现状.作为相对比较新的平面图染色研究方向,我们做的主要工作是研究了平面图的Injective染色数在围长至少为5时的最优值.在后面的章节里面详细讨论了Injective染色数为△+4的充分条件.
【学位授予单位】：浙江师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】

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

1 王超;平面图的injective染色[D];浙江师范大学;2016年

2 陆凯;平面图的injective染色[D];浙江师范大学;2013年

3 杨胜;平面图的Injective染色[D];浙江师范大学;2014年

，

本文编号：1219819