几类图的g-边覆盖染色

发布时间：2018-02-22 02:44

  本文关键词： 边染色 边覆盖染色 g-边覆盖染色 g-边覆盖染色数 g-边覆盖临界图 几乎二部图　出处：《山东师范大学》2017年硕士论文　论文类型：学位论文

【摘要】：设G是一个简单图,C是一个颜色集.一个图G的正常边染色是给图G的边分配颜色使得每种颜色在G的每个点处至多出现一次.一个图G的边覆盖染色是用颜色集C中的颜色给G的边染色使得每种颜色在每个点处至少出现1次.一个图G的g-边覆盖染色是图的边覆盖染色的推广,它是用颜色集C中的颜色给G的边染色使得每种颜色在每个点v∈V(G) 处至少出现g(v)次,这里g是定义在顶点集上的非负整值函数,即对任意的点v ∈ V(G),0≤g(v)≤d(v).图G的g-边覆盖染色数是使得G有g-边覆盖染色的最大的颜色数目,用Χgc1(G)来表示.宋慧敏和刘桂真在2005年的一个结果表明:任意一个简单图G的g-边覆盖染色数Χgc1(G)=δg(G)或δg(G) - 1,其中δg(G)=(?).如果Χgc1(G)=δg(G),那么称图G为g-边覆盖染色第一类的,否则称图G为g-边覆盖染色第二类的.这种确定简单图G是g-边覆盖染色第一类的还是第二类的问题称为图G的g-边覆盖染色的分类问题.本论文主要研究了几类图的g-边覆盖染色,首先研究了g 边覆盖临界图的一些性质,我们找到了g-边覆盖临界图的一个新的必要条件,该结论严格推广了王纪辉等人在2007年的一个结论以及宋慧敏和刘桂真在2004年的一个结论.接着又研究了几乎二部图的g-边覆盖染色问题,我们得到了一个几乎二部图是g-边覆盖第一类图的一些新的充分条件,我们的某些结果严格推广了王纪辉等人在2006年的一个结论以及李金波和刘桂真在2011年的一个结论.本文分四章进行讨论.第一章主要介绍了图的染色问题的研究背景和意义,给出了文章中涉及的一些基本概念和符号,并阐述了边覆盖染色和g-边覆盖染色理论的研究现状,列出了本论文的主要结果.第二章主要介绍了研究本论文所用到的基本工具,列出了本论文用到的一些重要的引理及其推论.第三章主要讨论了几类图的g-边覆盖染色,对所得到的结论进行了详细的证明,并给出了相关的推论.第四章给出进一步可以研究的问题.
[Abstract]:Let G be a simple graph C is a color set. The normal edge coloring of a graph G is to assign the color to the edge of graph G such that each color appears at most once at each point of G. the edge covering coloring of a graph G is coloring with color. The color in the set C gives the edge coloring of G so that each color appears at each point at least once. The G-edge covering coloring of a graph G is a generalization of the edge covering coloring of a graph. It coloring the edges of G with the colors in the color set C so that each color appears at least at every point v 鈭，

本文编号：1523455