图的边染色及一些有限制条件的染色

发布时间：2021-07-12 00:03

　　图的染色问题在图论及理论计算机科学中都有着极为广泛的应用,是图论研究中最重要的课题之一.在本论文中,我们研究图的边染色及一些简单图的有限制条件的染色.设G是可能具有重边但不具有环的图,分别用V,E,△和μ表示G的顶点集,边集,最大度和重数.本文的第一章给出图的边染色,点染色及其它一些有限制条件的染色的定义,并给出相关问题的一些主要研究进展和猜想.图的边染色的核心问题是确定其边色数.图G的k-边染色φ是从E到集合{1,2,…,k}（其中的元素称为颜色）的一个映射,使得任意两条相邻边的颜色不同.G的边色数是使得G存在k-边染色的最小正整数k,记作χ’与研究边染色相比,研究分数边染色更加容易一些.图G的分数边染色是G的匹配的集合M（G）的一个非负赋权ω（.）,使得对每条边e∈E,有∑M∈M:e∈Mw（M）=1显然这样的赋权ω（.）存在.G的所有分数边染色中最小的总权值∑m∈Mw（M）称为是G的分数边色数,记作χ’f,计算χ’f是多项式时间的.图G的边色数与分数边色数的关系如下△≤x’f ≤x’≤△+μ,其中的上界为Vizing的一个经典结果.事实上,如果χ’f>△,那么x’f=max|... 

【文章来源】：山东大学山东省 211工程院校 985工程院校 教育部直属院校

【文章页数】：86 页

【学位级别】：博士

【部分图文】：

图５．３：断言５．２．３的说明??


本文编号：3278770