论文部分内容阅读
图的染色问题在图论及理论计算机科学中都有着极为广泛的应用，是图论研究中最重要的课题之一.在本论文中，我们研究图的边染色及一些简单图的有限制条件的染色.设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的分数边色数，记作xf，计算x7是多项式时间的.图G的边色数与分数边色数的关系如下:△≤xf≤x≤△+μ，其中的上界为Vizing的一个经典结果.事实上，如果xf＞△，那么xf=max|E(H)|/|V(H)|/2]，其中的最大取遍G的导出子图H.Goldberg(1973)，Andersen(1977)和Seymour(1979)各自先后猜想当x≥△+2时，x=[xf].这一猜想可推出Gupta(1967)在其博士毕业论文中的一个猜想，通常被称为Goldberg猜想或Goldberg-Andersen-Seymour猜想.本文的第二章，我们证明若x＞△+3√△/2，则x’=[xf].这之前最好的结果是由Scheide和由陈冠涛，郁星星，臧文安分别独立地得到的x＞△+√△/2的图.Goldberg猜想的一个等价猜想是下面的Jakobsen猜想:对任意正整数m(m≥3)，每个x＞m/m+1△+m-3/m-1的图G满足x=[xf].在过去的四十年中，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}.它为邻和可区别的边染色猜想的一个特例. 在本文的第六章，我们将对全文进行总结，并提出在图的染色问题中一些今后可继续研究的课题.