平面图的injective染色

来源 :浙江师范大学 | 被引量 : 1次 | 上传用户:houqiusheng
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文研究有限简单图.图G的一个injecdve k-染色是指映射φ:V(G)→{1,2,….,k},使得G中有公共邻点的两个顶点u,v满足φ(u)≠φ(v).如果图G有一个injectivek-染色,则称图G是injectivek-可染的.使得图G有一个injectivek-染色的最小k值称为G的injective色数,记作xi(G).用xli(G)表示图G的injective列表色数.  图的injective染色是南Hahn等人在2002年基于复杂理论的研究提出的.他们研究了超立方体的injective色数,并将其运用到编码纠错理论中.Injective染色与图的L(0,1)-标号以及平方图染色有着密切联系.2010年,Lu(z)ar提出了关于平面图的一个猜想:设G是平面图,若△=3,则xi(G)≤5;若4≤△≤7,则xi(G)≤△+5;若△≥8,则xi(G)≤([)3△/2」+1.猜想的上界能够达到.  本论文分为四章,主要研究了在不含短圈条件下的平面图的injective染色,所得结论改进了现有的一些结果,同时肯定了上述部分猜想.第一章介绍了本论文所涉及的有关定义,并对injective染色的研究现状和存在的问题做了一个综述.第二章主要讨论围长至少为5的平面图的injective列表染色.第三章分别讨论了xli(G)≤△+1和xli(G)=△的充分条件.第四章给出一个不含3-,4-,8-圈平面图的injective列表色数的较小上界.
其他文献
本文依据舌状绦虫疾病的传播过程,构建了两个动力学模型,并对其性态加以分析.  第一章,介绍了舌状绦虫病的生物背景和传播机制,以及寄生虫感染食饵一捕食者系统的动力学模型研
本文研究一类耦合反应扩散系统的边界控制问题.该系统是常微分方程与偏微分方程组的耦合,偏微分方程组包含了反应、扩散、对流等项.系统边界有热量交换且符合傅里叶定律.该系
学位
学位
数论函数是数论研究领域的一个重要的研究课题,而数论函数的均值问题又是广大数论专家和学者的一个常做的方面.因此,本文就一些Smarandache数论函数的均值问题进行了一些简单的
我们通常用一个连通的无向图G=(V,E)表示互连网络的拓扑结构,图G的顶点代表网络中的组件,图G的边代表网络中组件之间的通信联系.对互连网络的研究是并行和分布式计算机系统中的