几乎正则图的f-色类与gc-色类的关系

来源 :山东师范大学 | 被引量 : 0次 | 上传用户:hjzxxhjzxx
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
令C是一个颜色集.图G的边染色是颜色在图G的所有边上的一个分配.令G是一个图,一个图G的正常边染色是G的边染色使得G的每个点处不能有相同的颜色.一个图G的边覆盖染色是G的边染色使得每种颜色在每个点出至少出现一次.一个图G的∫-染色和gc-染色分别是正常边染色和边覆盖染色的推广.令∫和y是两个函数,在每个点v∈ V(G)处分别分配一个正整数∫(v)和一个非负整数g(v).—个图G的∫-染色是G的边染色使得每个点v∈ V(G)处最多有∫(v)条边染相同的颜色.图G的先-染色是G的边染色使得每种颜色出现在每个点v∈ V(G)处至少有g(r)次.清晰地,图G有∫-边染色当且仅当对任意点v∈ V(G)有0 g g(v)< d( v).在这篇论文中,我们总是假设对任意点v∈ V(G)有0< g(v)< d( v).将图G进行∫-染色所需要的最小的颜色数目被称为图G的/-染色数,记作x f(G).相对地,将图G进行&-染色所需要的最大的颜色数目被称为图G的∫-染色数,记作xf(G)。(G).当∫=1时,∫-染色恰好是正常边染色;当G=1时,gc-染色的确是边覆盖染色.因为正常边染色问题是NP-完备的(即使是对于立方图来说),所以∫-染色问题和gc-染色问题也是NP-完备的.1986年Hakimi和Kariv证明:任意简单图G有xf(G)=△ f(0)或△f(G)+1,这里(此处公式省略).如果(此处公式省略),称G为∫-染色第一类图,否则称G为∫-染色第二类图.这种确定简单图的∫-染色数的问题称为∫-染色的分类问题.宋慧敏和刘桂真在2005年给出的一个结果表明:任意简单图G有(此处公式省略)这里(此处公式省略).如果Xg。(G)=(G),称G为gc-染色第一类图,否则称G为gc-染色第二类图.这种确定简单图的gc-染色数的问题称为&-染色的分类问题.本论文主要研究了几乎正则图的∫-染色的分类问题以及/-色类与先-色类之间的关系,张霞2015年证明了对于任意的正则图G来说,当G的∫-核与gc-核是相同的,并且对于/-核或&-核里的每个点v都有∫(v)= g( v),那么在∫-色类与gc-色类之间总是有一致性的结果.然而,对于其它的图(甚至是几乎正则图)来说,在∫-色类与gc-色类之间不是总是一致的.本论文对几乎正则图,当满足∫-核与gc-核是相同的,并且对任意∫-核或fit-核里的点v有∫(v)= g(v)时,给出了∫-色类与gc-色类之间有一致性分类结果的一些充分条件.  本文分为四章进行了讨论.在第一章中,介绍了研究背景以及研究意义,给出了本文中用到的基本概念与符号,给出了几类图的∫-色类与gc-色类的关系的研究现状和本文关于几乎正则图研究的主要结果;在第二章中,介绍了本文要用到的预备知识,包括主要的基本工具以及主要的引理;在第三章中,讨论了几乎正则图的∫-色类与A-色类的关系,先给出了几乎正则图的∫-染色分类的几个结论,然后给出/-核或fit-核分别在r-度点集和r+1-度点集内∫-色类与&-色类关系的结论;在第四章中,给出了本论文可进一步研究的问题.
其他文献
设G是一个简单图,C是一个颜色集.一个图G的正常边染色是给图G的边分配颜色使得每种颜色在G的每个点处至多出现一次.一个图G的边覆盖染色是用颜色集C中的颜色给G的边染色使得每
线性半无限规划(LS I P)问题是一类约束变量个数有限而指标个数无限,即约束条件个数无限的优化问题.由于其在金融、博弈论、概论论与数理统计、通信网络和优化问题等各领域中
设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(