1-平面图的非正常染色的研究

来源 :山东师范大学 | 被引量 : 0次 | 上传用户:Lu153
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文仅考虑有限,简单的无向图.  设 d1…,d k是 k个非负整数.图 G=(V,E)称为是非正常(d1???,dk)-可染的,或(d1…,dk)-可染的,当且仅当G的点集可以被剖分成V1,…,Vk,使得每个 M的点导出子图G[V]中点的最大度至多为d1,1< i< k.当 d1=…= dk=0时,即为正常k-染色.  一个图 G称为是1-平面图的,如果它可以被画在平面上使得每条边至多交叉另外一条边.1-平面图的概念由Ringel提出,并猜想每个1-平面图都是6-可染的,这已被Borodin(1986)证明.因为存在一个7-正则的1-平面图,所以界6是紧的.在2005年,任意的一个1-平面图是否是(0,0,0,0)-可染的被证明是NP-完备的.  作为图的正常点染色的一种推广,非正常点染色问题已经被广泛研究.1976年,Steinberg提出猜想:每个不含4-圈和5-圈的平面图是(0,0,0)-可染的.在这一猜想的推动下,得到了许多著名结果,例如,每个不含4-圈和5-圈的平面图是(2,1,0)-和(4,0,0)-可染的等.  本文将平面图的非正常染色推广到1-平面图中,在平面图的非正常染色问题的启发下,我们主要讨论不含长度为3,4,5和6的圈的1-平面图,即围长至少是7的1-平面图的非正常点染色问题.第一章介绍了本论文所涉及的有关定义,并对平面图的非正常染色和1-平面图的染色的研究现状做了综述.在第二章和第三章中,我们假设1-平面图 G已经被嵌入到一个平面上使得它的每条边至多交叉另外一条边,通过将G中边的交叉转化成新的4-点,得到其关联平面图G*,并且称G*中新的4-点为交叉点.根据1-平面图 G及其关联平面图G*的结构性质,我们利用权转移的方法分别证明了围长至少是7的1-平面图是(1,1,1,0)-和(2,0,0,0)-可染的.
其他文献
设G是一个连通图,其顶点集合为V(G).对G中任意两个顶点i和j,i和j之间的距离定义为连接这两个顶点之间的最短路的长度,而i和j之间得电阻距离定义为用单位电阻代替G中的每条边
近似移动最小二乘(AMLS)方法是一种新型的无网格方法,具有精度高、计算简单、易实现等特点。本文详细介绍了AMLS方法及其在微分方程中的应用。给出了两种求解微分方程的AMLS方法
本文首先介绍了生物信息学的产生背景、发展概况、研究内容以及基因组信息学的一些相关知识,具体介绍了DNA碱基序列和蛋白质序列的混沌游戏表示方法,以及怎么构造系统发生树等
本文主要讨论巴拿赫空间中线性非自治脉冲微分方程的非线性扰动问题.本文中的关键点是我们假设线性非自治脉冲微分方程具有一种新型的非一致二分性-称为非一致(μ,v)-二分性.在
本文考虑一组3维有界区域上带耗散能量项的Boussinlesq方程组,是不均匀不可压Navier-Stokes方程方程与内能方程的耦合.内能方程中有强非线性项lD(u)12,D(u)为形变张量.本文证明该
在这篇文章中,我们利用新的方法研究下列两个偏泛函积分微分方程的柯西问题(公式略)。  其中当t≥0时,A(t)是稠密域D(A)上不依赖于t的闭线性算子,对于0≤s≤t,s(t,s)是区域D(S)]D(
令C是一个颜色集.图G的边染色是颜色在图G的所有边上的一个分配.令G是一个图,一个图G的正常边染色是G的边染色使得G的每个点处不能有相同的颜色.一个图G的边覆盖染色是G的边染
本文考虑了一类带有有色噪声的拉格朗日系统的建模与跟踪控制问题.首先利用对无噪声干扰的机械系统建立确定性的拉格朗日方程.根据动静法和相对运动原理将环境中的振动转化为