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

摘要

图的染色问题在图论及理论计算机科学中都有着极为广泛的应用，是图论研究中最重要的课题之一.在本论文中，我们研究图的边染色及一些简单图的有限制条件的染色.设G是可能具有重边但不具有环的图，分别用V E，△和μ表示G的顶点集，边集，最大度和重数.
　　本文的第一章给出图的边染色，点染色及其它一些有限制条件的染色的定义，并给出相关问题的一些主要研究进展和猜想.
　　图的边染色的核心问题是确定其边色数.图G的k-边染色ψ是从E到集合{1，2，…，k}（其中的元素称为颜色）的一个映射，使得任意两条相邻边的颜色不同.G的边色数是使得G存在k-边染色的最小正整数k，记作x'.与研究边染色相比，研究分数边染色更加容易一些.图G的分数边染色是G的匹配的集合M(G)的一个非负赋权w(.)，使得对每条边e∈E，有ΣM∈M∶e∈Mw(M)=1.显然这样的赋权w(.)存在.G的所有分数边染色中最小的总权值∑M∈Mw(M)称为是G的分数边色数，记作x'f，计算x'7是多项式时间的.图G的边色数与分数边色数的关系如下:△≤x'f≤x'≤△+μ，其中的上界为Vizing的一个经典结果.事实上，如果x'f＞△，那么x'f=max|E(H)|/|V(H)|/2]，其中的最大取遍G的导出子图H.Goldberg(1973)，Andersen(1977)和Seymour(1979)各自先后猜想当x'≥△+2时，x'=[x'f].这一猜想可推出Gupta(1967)在其博士毕业论文中的一个猜想，通常被称为Goldberg猜想或Goldberg-Andersen-Seymour猜想.本文的第二章，我们证明若x'＞△+3√△/2，则x’=[x'f].这之前最好的结果是由Scheide和由陈冠涛，郁星星，臧文安分别独立地得到的x'＞△+√△/2的图.Goldberg猜想的一个等价猜想是下面的Jakobsen猜想:对任意正整数m(m≥3)，每个x'＞m/m+1△+m-3/m-1的图G满足x'=[x'f].在过去的四十年中，Jakobsen猜想被证得对至多为15的m是成立的.我们证明它在m≤23时成立.此外，我们证明Goldberg猜想对△≤23或|V|≤23的图G成立.
　　重数μ≤1的图G称为是简单的.简单图G的k-点染色ψ是从V到集合{1，2，…，k}（其中的元素称为颜色）的一个映射，使得相邻点的颜色不同.使得G存在k-点染色的最小正整数k叫做G的点色数.由于确定G的点色数是NP-难的，可将点染色的条件放松，定义树染色如下.简单图G的k-树染色ψ是颜色1,2，…，k对G的顶点的一个分配，使得G的染每种颜色的顶点导出的子图是森林.G的点荫度va是使得G存在k-树染色的最小正整数k.吴建良，张欣和李海伦考虑树染色在均匀时的情形，即任意两个色类所含的顶点数至多差1.他们猜想任意简单图G的顶点集可均匀地被划分为m个子集，使得每个子集导出的子图是森林，其中m≥[△+1/2]是整数.本文第三章我们证明该猜想对5-退化图是成立的.
　　若去掉k-边染色的定义中相邻边的颜色不同这一条件，则得到k-边赋权的定义.2004年，Karo(n)ski, Luczak和Thomason猜想每个简单图G存在使用颜色为1，2,3的3-边赋权，使得任意两个相邻顶点关联边的赋权的和不同.这一猜想被称为1-2-3猜想.本文的第四章我们证明1-2-3猜想在把边赋权导出的点染色放松到树染色时是成立的.进一步地，我们给出一些具有树可染的2-边赋权的图类.
　　简单图G的邻和可区别的k-边染色是G的一个k-边染色，使得对任意边uv∈E，与u关联的边的颜色之和异于与v关联的边的颜色之和.用ndiΣ表示G存在邻和可区别的k-边染色的最小的正整数k.Flandrin等人猜想对任意至少6个顶点的简单图G，有ndiΣ≤△+2.这一猜想被称为是邻和可区别的边染色猜想.G的最大平均度mad(G)=max{2|E(H)|/|V(H)|:H是G的非空子图}.在本文的第五章，我们得到对不含孤立边且mad(G)＜8/3的简单图G，有ndiΣ≤k，其中k=max{△+1，6}.它为邻和可区别的边染色猜想的一个特例.
　　在本文的第六章，我们将对全文进行总结，并提出在图的染色问题中一些今后可继续研究的课题.

目录

声明

摘要

第一章 绪论

§1．1 基本定义和符号

§1．2 一些基本图类

§1．3 图的一些基本染色及有限制条件的染色

§1．3．1 边染色与分数边染色

§1．3．2 点染色与树染色

§1．3．3 均匀点染色与均匀树染色

§1．3．4 点可染的边赋权与树可染的边赋权

§1．3．5 邻和可区别的边染色与邻点可区别的边染色

第二章 多重图的边染色

§2．1 主要结果

§2．2 基础理论

§2．2．1 基本概念和定义

§2．2．2 基本集和闭集

§2．2．3 Tashkinov树

§2．3 Tashkinov树的扩展

§2．3．1 定义和基本性质

§2．3．2 主要结果

§2．4 关于Goldberg猜想和Jakobsen猜想的两个结果

§2．4．1 多重图在渐近条件下的边色数

§2．4．2 关于Jakobsen猜想的结果

第三章 5-退化图的均匀点荫度

第四章 1-2-3猜想的一个放松情况

§4．1 树可染的边赋权的一个上界

§4．2 特殊图的树可染的边赋权

第五章 具有小的最大平均度的图的邻和可区别的边染色

§5．1 主要结果

§5．2 稀疏图的邻和可区别的边染色

第六章 总结与展望

符号说明

参考文献

作者简介

攻读博士学位期间完成论文情况

致谢