论文部分内容阅读
设G是一个简单图,C是一个颜色集.一个图G的正常边染色是给图G的边分配颜色使得每种颜色在G的每个点处至多出现一次.一个图G的边覆盖染色是用颜色集C中的颜色给G的边染色使得每种颜色在每个点处至少出现1次.一个图G的g-边覆盖染色是图的边覆盖染色的推广,它是用颜色集C中的颜色给G的边染色使得每种颜色在每个点v∈V(G)处至少出现y(v)次,这里y是定义在顶点集上的非负整值函数,即对任意的点v∈ V(G),0< g(v)< d( v).图G的g-边覆盖染色数是使得G有g-边覆盖染色的最大的颜色数目,用( G)来表示.宋慧敏和刘桂真在2005年的一个结果表明:任意一个简单图G的g-边覆盖染色数(G)= g(G)或(G)-1,其中(此处公式省略).如果XL(G)= g(G),那么称图G为g-边覆盖染色第一类的,否则称图1G为g-边覆盖染色第二类的.这种确定简单图G是g-边覆盖染色第一类的还是第二类的问题称为图G的g-边覆盖染色的分类问题.本论文主要研究了几类图的g-边覆盖染色,首先研究了g-边覆盖临界图的一些性质,我们找到了g-边覆盖临界图的一个新的必要条件,该结论严格推广了王纪辉等人在2007年的一个结论以及宋慧敏和刘桂真在2004年的一个结论.接着又研究了几乎二部图的g-边覆盖染色问题,我们得到了一个几乎二部图是g-边覆盖第一类图的一些新的充分条件,我们的某些结果严格推广了王纪辉等人在2006年的一个结论以及李金波和刘桂真在2011年的一个结论. 本文分四章进行讨论.第一章主要介绍了图的染色问题的研究背景和意义,给出了文章中涉及的一些基本概念和符号,并阐述了边覆盖染色和g-边覆盖染色理论的研究现状,列出了本论文的主要结果.第二章主要介绍了研究本论文所用到的基本工具,列出了本论文用到的一些重要的引理及其推论.第三章主要讨论了几类图的g-边覆盖染色,对所得到的结论进行了详细的证明,并给出了相关的推论.第四章给出进一步可以研究的问题.