论文部分内容阅读
设G是一个图,C是一个颜色集.一个图G的正常边染色是给图G的边分配颜色使得G的每个点处不能有相同的颜色出现.一个图G的边覆盖染色是用颜色集C给G的边染色使得每个点处每种颜色至少出现1次.一个图G的g-边覆盖染色是图的边覆盖染色的推广,它是用颜色集C给G的边染色使得每种颜色在每个点v∈V(G)至少出现g(v)次,这里g是从V(G)到正整数集的一个函数.使得G有一个k色的g-边覆盖染色的最大的k称为G的g-边覆盖染色数,记为χgc(G).宋慧敏和刘桂真教授[18]的一个结果表明:任意简单图G有χgc(G)=δg(G)-1 或δg(G),这里δg(G)=minv∈V(G){[d(v)/g(v)]}如果χgc(G)=δg(G),称G为g-边覆盖染色第一类图,否则称G为g-边覆盖染色第二类图.这种确定简单图的g-边覆盖染色数的问题称为g-边覆盖染色的分类问题.本论文主要研究图的g-边覆盖染色的分类问题,我们将张霞和刘桂真教授[26]在2011年给出的边覆盖染色里的结果推广到g-边覆盖染色当中,又将此结果的条件弱化,得到一个g-边覆盖染色第一类图的新的充分条件.该结论推广了宋慧敏和刘桂真教授[18]的一个结论.另外,我们将S.Akbari等人[1]在正常边染色里的一个结果部分推广到g-边覆盖染色当中,得到两个g-边覆盖染色第一类图的充分条件. 本文分为四章进行讨论. 在第一章,介绍研究背景和意义,给出论文中用到的概念和符号,并说明g-边覆盖染色的研究进展和本论文的主要结果. 在第二章,介绍本论文所用到的基本工具,并简要说明它们的作用;列出本论文中用到的重要的引理及其推论. 在第三章,讨论几类关于g-边覆盖染色第一类图并对结论进行证明. 在第四章,给出可进一步研究的问题. 本文的主要结果如下: 定理1 令G是一个简单图,关联一个正整函数g:V(G)→Z+,且δg(G)≥2.若G是弱-δg(G)-可剥离的,那么G是9-边覆盖染色第一类的. 定理2 令G是一个简单图,关联一个正整函数g:V(G)→Z+,且δg(G)≥2.若G不是弱-δg(G)-可剥离的,但G的剩余子图的度恢复图有一个δg(G)色的一般的g-边覆盖染色,那么G是g-边覆盖染色第一类的. 定理3 令G是一个简单图,关联一个正整函数g:V(G)→Z+,且δg(G)≥2,H是G利用弱-δg(G)-可剥离算法剥离若干点后得到的非空子图.如果H的度恢复图有一个δg(G)色的一般的g-边覆盖染色,那么G是g-边覆盖染色第一类图. 定理4 令G是一个连通简单图,关联一个正整函数g:V(G)→Z+.如果Gδg的每个分支都是单圈图或者树,且这些单圈图都不是圈,那么G是g-边覆盖染色第一类的. 定理5 令G是一个连通简单图,关联一个正整函数g:V(G)→Z+如果Gδg的每个分支都是单圈图或者树,至多有一个单圈图是圈且Gδg不是圈,那么G是g-边覆盖染色第一类图.