论文部分内容阅读
图的染色理论是图论中的一个重要分支．图的染色种类有很多，诸如边染色、点染色、面染色和全染色等．其中研究最多，结果也较完善的就是图的边染色．图的正常的边染色就是把图的边集分解为一些互不相交的边的独立集的并的方法．在图的正常边染色理论中有著名的Vizing定理，而其中关于正常边染色的图的分类问题一直是研究的热点．近年来，人们开始考虑把图的边集分解为其它形式，得到一些推广的边染色并进行研究．本文主要是讨论了图的边覆盖染色、f-边覆盖染色、分数边覆盖染色和分数边染色等．
我们用Ｇ(Ｖ,Ｅ)表示一个图，其中Ｖ是顶点集，Ｅ是边集．设S是一个集合，｜S｜表示集合S的基数．在本文中我们所说的图通常指有限简单图．如果图G中允许有重边则称G为重图．对图G中的点υ，用d<,G>(υ)表示顶点υ的度，用N<,G>(υ)表示υ的邻点集δ(G)＝min{d<,G>(υ)：υ∈Ｖ(G)}，Δ(G)＝maX{d<,G>(υ)：υ∈Ｖ(G)｝，则δ(G)和Δ(G)分别表示图G的最小度和最大度．在不产生混淆的情况下，我们常用Ｖ，Ｅ，Ｎ(υ)，δ，Δ分别代替Ｖ(G)，E(G)，N<,G>(υ)，δ(G)，Δ(G)．
令G<,δ>表示图G中由最小度点导出的子图．如果Δ(G)＝δ(G)＝d则称G是d-正则图，通常也称3-正则图为立方图．如果图G的顶点集可以划分为两个互不相交的子集Ｖ<,1>和Ｖ<,2>且G的任何一条边的两个端点分别在Ｖ<,1>和Ｖ<,2>中，则称图G为二部图．若图G中存在一点u使得G—u是一个具有二划分为(Ｘ，Ｙ)的二部图则称G为近似二部图，记为G(Ｘ，Ｙ；u)．一个圈是指图中每个点的度都是2的连通图，称含有奇数条边的圈为奇圈，含有偶数条边的圈为偶圈．
我们用正整数1，2，…来表示颜色，若Ｃ是边集E到集合{1，2，…，к}的映射，即Ｃ：Ｅ→{1，2，…，к}，则称Ｃ为图G的к-边染色．令G<,i>(υ)表示在图G的在染色C中与顶点υ关联的染i色边的数目．假定对Ｖ中每个顶点υ都已赋以正整数f(υ)且要求1≤f(υ)≤d(υ)．若染色C使图G中任意顶点υ∈Ｖ和i∈{1，2，…，к}，都有C<,i>(υ)≥f(υ)成立，则称C为图G的f-边覆盖
（上面有化学方程式）由上面的式子知，图G的f-边覆盖色数x＇<,fc>(G)要么等于δ<,f>-1，要么等于δ<,f>，由此我们根据x＇<,fc>(G)把图分为两大类：若x＇<,fc>(G)=δ<,f>则称G是c<,f>I类的，否则称G是c<,f>ll类的．若对所有的顶点υ，都满足f(υ)=1，此时δ<,f>=δ，则图G的f-边覆盖染色就是通常讨论的一般的边覆盖染色．对图G进行边覆盖染色所需的最大颜色数(求最小没有意义)称为图G的边覆盖色数，记为x＇<,c>(G)．类似的，对于边覆盖染色同样也有分类问题，即若x＇<,c>(G)=δ则称G是CI类的，否则称G是Cll类的．对于正则图而言，其边覆盖染色的分类问题等价于正常的边染色分类问题．因此，边覆盖染色的分类问题也是ⅣP-完全的．对任意的图讨论它的边覆盖染色分类是很困难的，但对一些特殊图讨论其分类是可能的．讨论图的分类问题时，“临界”的概念是很重要的．设G是连通的非完全图且x＇<,fc>(G)=δ<,f>-1，如果对任意的u，υ∈V，e=uυ E都有x＇<,fc>(G+e)=δf成立，则称G是f-边覆盖临界的．同样，若对所有的顶点υ取。f(υ)=1，则有边覆盖临界图的概念．而研究f-边覆盖临界图(或边覆盖临界图)的性质与构造对于解决图的基于f-边覆盖染色(或边覆盖染色)的分类问题具有重要意义． 另一方面，分数边覆盖染色和分数边染色也是近几年出现的新的研究方向．而且，分数边覆盖色数和分数边色数分别对讨论图的边覆盖染色分类和正常边染色分类有重要的作用．因此，讨论图的分数边覆盖染色和分数边染色也是非常有意义的．
图G的分数边覆盖染色是指给G的每一个边覆盖C分配非负权ωc，使得对任意的e∈E(G)满足∑c ωc≤1(其中∑c e是对含边e的G的所有的边覆盖求和)，相应的分数边覆盖色数x<,c>(G)是指可进行分数边覆盖染色的∑cωc(是对G的所有的边覆盖c求和)的最大值．
类似地，图G的分数边染色是指给G的每一个边匹配M分配非负权ωM，使得对任意的e∈E(G)满足∑M eωM≥1(其中∑M e。是对含边e的G的
所有的匹配求和)，相应的分数边色数x<,f>(G)是指可进行分数边染色的∑<,M>ωM(是对G的所有的匹配M求和)的最小值。 关于图的边覆盖染色的结论与图的正常边染色的结论有很多是类似，但是其本质上有很大的不同，很多结论无法从正常边染色的结论中推出来．对二者进行研究所用的方法和手段也有很大的不同，其研究是相对独立的。
本文分为五章.第一章介绍了图论的基本概念和边染色的历史和发展状况，给出了一个简短但相对完整的综述．第二章讨论了边覆盖染色的分类，首先是给出一般图是CI或CII类图的一些充分条件，然后又对某些特殊图的分类进行了讨论得到一些有意义的结果，最后对边覆盖临界图的性质和构造进行了讨论，给出了一种构造边覆盖临界图的构造方法。第三章我们首次对f-边覆盖染色的分类和f-边覆盖临界图的性质进行了研究，得到许多比一般的边覆盖染色更强的一些结果。在第四章首先介绍了分数边覆盖色数的定义并在原有结果的基础上给出了一个更为精确的分数边覆盖色数计算公式．还讨论了分数边覆盖色数和边覆盖色数的关系，对于图的边覆盖染色的分类有重要意义。第五章我们首先介绍了分数边色数的定义并讨论了特殊图的分数边色数，对于图的正常边染色中某些猜想我们还讨论了其在分数边染色中的正确性。