论文部分内容阅读
令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-度点集内∫-色类与&-色类关系的结论;在第四章中,给出了本论文可进一步研究的问题.