图的圈和路因子理论的若干结果及对平面图中全染色猜想的研究

论文摘要

本文考虑的图若无特殊声明均为简单、无向有限图，对于一个图G=G（V（G），E（G）），我们用V（G）和E（G）分别表示图的顶点集合和边集合。对任意的v∈V（G），我们用dG（v）表示顶点v在G中的度数。△（G）和δ（G）分别表示图G的最大度和最小度，在不引起混淆的情况下简记为△和δ。对于图G，我们用|G|=|V（G）|表示G的阶数，即G的顶点数，并定义图G中两个不相邻的顶点的最小度和为：σ2（G）=min{dG（x）+dG（y）|x，y∈V（G），x≠y，xy（?）E（G）}。（若G是一个完全图，则令σ2（G）=∞）。对于二部图G，令G的两个部分的顶点集合分别为V1和V2。若|V1|=|V2|，则称G为均衡二部图。定义δ1，1（G）=min{dG（x）+dG（y）|x∈V1，y∈V2}，σ1，1（G）=min{dG（x）+dG（y）|x∈V1，y∈V2，xy（?）E（G）}。(若G是一个完全二部图，则令σ1，1=∞)。对图G中任意点u，u的（开）邻域及闭邻域分别如下定义：Na（u）={x∈V（G）|xu∈E（G）}，NG[u]={u}∪NG（u）。完全二部图K1，3称为一个爪，如果G不含同构于K1，3的生成子图，则称G是无爪图。对于图G中的一条路P和一个圈C，定义路和圈的长度分别为：l（P）=|V（P）|-1，l（C）=|V（C）|。对于任意两点x，Y∈V（G），x到y的最短路的长度叫做从x到y的距离，记为d（x，y）。当d（x，y）=2时我们定义J（x，y）={u∈NG（z）∩NG（y）|NG[u]（?）NG[x]∪NG[y]}。给定图G，如果对于G中距离为2的任意两点x，y都满足J（x，y）≠（?），则称G是半无爪图。显然，每个无爪图都是半无爪的，但并不是每个半无爪图都是无爪图。无爪图是一类非常有趣的图，半无爪图是无爪图的放松。所以把在无爪图中成立的结论推广到半无爪图中来研究是非常有意义的。图的一个路因子就是指每一个分支都是一条路的一个生成子图。给定一个正整数k，P≥k-因子就是指每个分支都至少含k个顶点的一个路因子。G的一个哈密顿圈是G的包含G中所有顶点的一个圈。G的一个1-因子是G的一个1-正则支撑子图，通常我们称1-因子为完美对集或完美匹配。显然G的一个1-因子是覆盖G的所有顶点的一个边集合。G的一个2-因子是G的一个2-正则支撑子图，易见2-因子的每一个连通分支为一个圈。图的k个独立圈是指G中k个顶点不相交的圈。图的独立圈、2-因子和路因子问题是图的因子理论中非常重要的一部分，也是图的哈密顿圈理论的推广和延伸。它是图论中非常有趣的一类问题，也是国内外研究的热门课题。其理论研究日益成熟和完善，而且它在计算机科学、通信网络设计等中都有重要应用。关于图的独立圈、2-因子和路因子理论的研究主要集中在以下几个方面：图中含指定个数的独立圈和2-因子；含指定长度的独立圈和2-因子；图中具有指定性质的独立圈和2-因子；具有指定性质的路因子等等。全文共分四章。第一章简单介绍了图论的基本概念，圈和路因子理论的历史和发展状况及一些已有的相关结论。这一章是第二章和第三章的基础。第二章讨论了二部图中包含指定顶点的独立圈的部分结果。其主要结果如下：定理2．1．1．设k≥2，1≤s≤k，n≥2k+1。如果σ1，1（G）≥max「（4n+s+1）/3（?），n+k}，那么对任给的k个顶点v1，v2，…，vk，G含k个独立圈C1，C2，…，Ck使得：vi∈V（Gi），|Gi|≤6，且{C1，C2，…，Ck]。中至少有s个4-圈。定理2．2．1．设k≥1，0≤s≤k，n≥2k。如果δ（G）≥max{「（3n+3k-1）/6（?），「（2n+3s-1）/4（?），「（4n+7k）/10)（?）}，那么对任给的k个顶点v1，v2，…，vk，G含k个独立圈C1，C2，…，Ck使得：vi∈V（Gi），且|G|=4（1≤i≤s），|G|≤6（s+1≤i≤k）。关于路因子的研究，2002年，Kiyoshi Ando等人证明了下面的结论：如果图G是一个无爪图且满足δ（G）≥d，那么G中一定含有一个P≥d+1-因子。在第三章中本文证明了这样的结论：定理3．1．1．如果G是一个半无爪图，且δ（G）≥d，那么G中一定含有一个P≥d+1-因子。在本文的第四章中，我们在图论的染色方面作了改进。我们知道染色理论是图论中的另一个重要分支。图的染色种类也很多，例如：通常的边染色、点染色，面染色，全染色，列表染色和星染色等等。给定图G，G的k-全染色是指用k种颜色给G的点和边进行染色，使G的任意邻接点或邻接边均染不同的颜色，且G的任一点与该点的任一关联边均染不同的颜色。1964年，Vizing提出了著名的全染色猜想：任何一个图G都有一个（△+2）-全染色。但这一猜想至今尚未完全解决。本文第四章主要考虑了Vizing猜想的特殊情况。其主要结论如下：定理4．1．1．△=6且不含5-圈或6-圈的平面图G是可8-全染色的。另外，本文的后三章最后还提出了一些问题，以待进一步研究。

论文目录

• 中文摘要
• 英文摘要
• 符号说明
• 第一章 引言
• §1.1 基本概念
• §1.2 问题产生的背景及其进展情况
• §1.3 已有的结论及本文的主要结果
• 第二章 二部图中含指定顶点的独立4-圈
• 1,1（G）限制度条件下含指定顶点的独立4-圈'>§2.1 二部图中用σ_1,1（G）限制度条件下含指定顶点的独立4-圈
• §2.2 二部图中用δ（G）限制度条件下含指定顶点的独立4-圈
• §2.3 可进一步讨论的问题
• 第三章 半无爪图中的路因子
• ≥d+1^-因子'>§3.1 δ（G）≥d的半无爪图含有一个P_≥d+1^-因子
• §3.2 可进一步讨论的问题
• 第四章 最大度为6的平面图的全染色
• §4.1 △（G）=6且不含5-圈平面图的结构
• §4.2 △（G）=6且不含6-圈平面图的结构
• §4.3 △（G）=6且不含5-圈或6-圈的平面图可8-全染色
• §4.4 可进一步讨论的问题
• 参考文献
• 致谢
• 作者简介
• 学位论文评阅及答辩情况表