论文部分内容阅读
图论的研究始于200多年前．关于图论的第一篇论文是1736年Euler发表的，他用图的方法解决了哥尼斯堡(Konigsberg)七桥问题．二十世纪六十年代以来，图论在科学界异军突起，活跃非凡．图论中有很多著名的问题，如哈密尔顿问题，四色问题，中国邮递员问题等．并且，应用图论来解决化学，生物学，信息和计算机科学等学科问题已显示出极大的优越性．同时，图论在工程技术领域及社会科学中也有着广泛的应用．它作为离散数学的一个重要分支，受到了各方面的普遍重视．
我们用G表示一个图，若G的每条边都染上颜色，则称G为边染色图．给定一个边染色图G，关联于顶点u的不同颜色的边的数目，称为顶点u的色度，记为d(u)．如果把一般的未染色图看作是每条边都染不同颜色的边染色图，则顶点的色度就等于它的度．除了在图论和算法上的重要应用外，边染色中的许多问题还出现在分子生物科学，心理学和网络通信等其它的领域中．因此，近年来，这方面的研究变得活跃起来，主要集中在边染色图中某些特殊子图的存在性上．边染色图中的子图，如果任意相邻的两条边的颜色都不相同，我们称之为交错子图，或者称为边正常染色子图．进一步，如果该子图中所有边的颜色都不相同，我们称之为彩色子图．这两类子图的研究尤其受到关注．图的匹配，路和圈是图论中的基础研究领域，因此边染色图中的彩色的(交错的)匹配，路和圈就成了一个重要的研究方向．
图中过每个顶点的圈，称为图的哈密尔顿圈．图的哈密尔顿圈问题，是图论中的一个经典问题．其中一个著名的猜想是Chvátal[20]提出的如下猜想：韧度充分大的图有一个哈密尔顿圈．对于许多特殊的图类，例如弦图和平面图，上述猜想被证明是成立的[11，12，23]．图G的一条K-途径是指G的一条经过每个顶点至多七次的闭支撑途径．图的一个哈密尔顿圈就是图的1-途径．作为哈密尔顿圈的一个非常有趣的变形，图的K-途径引起了很多人的兴趣．Jackson和Wlormald[54]研究了K-途径，并猜想任意l-坚韧图都有一条2-途径．这个猜想仍然没有得到证明，最好的结果是任意4-坚韧图都有一条2-途径[37]．自然地，我们会考虑如下问题：确定最小的整数k：k(△)使得对最大度为△的任意图都有一条k-途径．对于一般图，这个问题是平凡的，因为最大度为△的任意树都有△-途径[54]，但对于k<△，不含任何七一途径．但如果我们考虑无桥图(2-边连通图)，情况就不一样了．我们在第五章中，讨论了这个问题．另一方面，图的染色理论在图论中占有很重要的地位．近年来，图的圆染色的研究变的异常活跃，得到了一系列漂亮的结果，也产生了许多新颖的研究方法，逐渐成为图的染色理论中的一个重要分支．图的选择数(列表色数)是图的一个很重要的参数，其中一个著名的定理是Thomassen[81]的关于平面图的5-可选择性的证明．最近，Zhu[89]和Mohar[69]给出了圆选择数的概念，因此，对平面图的圆选择数的研究也就成了一个非常有意义的研究方向．另外， Bokal等[69]考虑了有向图的圆染色，把色数和圆色数的概念推广到有向图．因此，许多关于无向图中的染色和圆染色方面的问题，我们都可以在有向图中考虑．
本文研究了图论中的几个问题，具体地，我们研究了边染色图中的匹配和圈，图的K-途径和图的圆染色．全文共分为七章．第一章，我们给出了一个简短但相对完整的综述．首先，我们给出了一些基本的定义和术语，并且对上述三个方向的研究进展分别做了介绍．最后，我们列出了本文的主要结果．
在第二章，我们考虑了边染色图中的彩色匹配问题．边染色图中的一个彩色匹配是指任意两条边的颜色都不相同的一个匹配．在一般的未染色图中，最大匹配问题(找一个边数最多的匹配)是多项式可解的([61])．而在边染色图中，即使是在边染色二部图中，最大彩色匹配问题(找一个边数最多的彩色匹配)是NP-完全的([45])．因此，彩色匹配的研究主要集中在边染色完全图和边染色完全二部图中．Erds和Pósa．[30]研究了极值图论中的一个很基本的问题，他们证明了任意一个顶点个数至少为2K，最小度至少为k的图，都有一个k条边的匹配．我们在边染色图中研究了类似的问题．我们证明了若G是一个边染色图，并且对任意点u都有d〈’C〉(U)≥K≥4，则G含有一个有条边的彩色匹配．我们还证明了若G是一个边染色二部图，并且对任意顶点U，都有d〈’C〉(U)≥K≥3，则G有一个条边的彩色匹配．并且，我们给出了色邻域的概念，研究了边染色二部图中，满足某种色邻域条件的彩色匹配问题．
在第三章，我们研究了边染色图中的彩色圈．首先，我们给出了边染色图存在彩色圈的色度条件．并且，我们运用关于Caccetta-Hggkvist猜想(有向图中有向三角形存在性)的一个结果，得到了边染色图存在彩色三角形或者彩色四边形的色度条件．同时，我们还研究了边染色图中的长彩色圈. 在第四章，我们讨论了边染色图中色度和交错圈的关系，得到了边染色图中几类特殊交错圈存在的色度条件．同时，我们还对Bollobás-Erdos猜想(边染色完全图中的交错哈密尔顿圈的存在性)做了研究，给出了满足Bollobás-Erdos条件的边染色完全图中，最长交错圈的圈长的一个下界．
在第五章，我们研究了图的κ-途径，证明了最大度为△的任意无桥图(2-边连通图)都有一条「(△+1)/2]．途径，并且证明了这个界是最好可能的.
在第六章，我们考虑Mohar[69]提出的关于平面图的圆选择数的一个问题，研究了具有大围长的平面图的圆选择数．我们证明了围长至少为(10n+8)/3的平面图的圆选择数至多为2+2/n，从而改进了[53]中的结果．另外，我们还讨论了几类特殊平面图(系列平行图，外平面图，奇轮)的圆选择数.
在第七章，我们沿用[71]中的定义，对有向图的染色和圆染色做了进一步的研究．我们证明了如果一个有向图D的补图不含有向的哈密尔顿圈，则D的圆色数X<,c>(D)等于它的色数X(D)．我们还得出，给定一个正常κ-染色的有向图D，κ=x(D)，则D中存在有向路过这κ种颜色．这些结果分别对无向图中的相应的结果做了推广．
另外，在每一章里面，我们都提出了几个可以进一步考虑的问题和未解决的猜想．