论文部分内容阅读
图论是离散数学的一个重要的分支，它在生产管理，军事，交通运输，计算机科学与技术，通信工程等领域都有着广泛的应用.1736年，Euler[14]发表的关于K(o)gsberg七桥问题的论文是图论领域的第一篇文章.后来，一些著名的图论问题相继被提出，如四色问题和中国邮递员问题等等.1878年，Sylvester[98]在《自然》上的一篇论文中首次提出了“图”这一名词.1936年，K(o)nig[71]出版了第一本图论专著《有限图和无限图理论》，从此图论成为数学的一个独立的分支. 一个图G定义为一个二元组(V(G)，E(G))，记为G=(V(G)，E(G))，其中V(G)是一个非空有限集，称为图G的顶点集;E(G)是定义在V(G)上的二元关系，称为图G的边集.本文所涉及到的图指的均是简单有限无向图.图G的补图用(G)来表示.我们分别用△(G)和δ(G)表示图G的最大度和最小度.图G的平均度为2|E(G)|/|V(G)|.图G的最大平均度mad(G)，为G的所有子图的平均度的最大值.如果能将图G画在平面上，使得它的边仅在端点处相交，则称G是可平面图. 本文主要研究图的极值问题和染色问题.在第一章，介绍了本文要用到的一些基本概念和符号.然后，对本文涉及到问题的背景，进展以及已知结果给出一个比较全面的综述. 在本论文的第一部分（第二章，第三章和第四章），考虑与树的存在性相关的一些极值问题.极值图论是图论研究的一个重要领域，它起源于1941年Turán的文章[101].在该篇文章中他得到了不包含r阶完全图Kr的n阶图的最大边数，并确定了相应的极图.1978年，Bollobás[15]的关于极值图论问题的专著《极值图论》的问世标志着极值图论的研究已形成相对完整的理论.1998年，Chung和Graham[31]的著作搜集了Erdós在极值图论和图论其他课题中提出的尚未解决的问题，将极值图论的研究推向了一个新的高度. 树是极小的连通图，是一类简单而又重要的图.1847年，Kirchhoff为了解电网络中一类线性方程组而提出了树这一概念.1857年，Cayley[25]在研究给定碳原子数为n的饱和碳氢化合物CnH2n+2的同分异构体时也发现了树，并提出了树的计数问题.此后，树在化学领域中发挥着日趋重要的作用.随着计算机科学的发展，树广泛应用于数据结构中，比如二叉查找树，堆，Trie树以及Huffman树等等.树是图的连通性理论中重要的子结构，一个图是连通的当且仅当其有支撑树. 考虑的问题是:在什么条件下，图G包含所有的k阶树？ 显然，若δ(G)≥k-1，则G包含所有的k阶树.若δ(G)≥k-1，则G中的边分布较为均匀.若不考虑G中边的分布情况，G的平均度大于k-2，G能否包含所有的k阶树？设G为平均度大于k-2的n阶图，则△(G)≥k-1，那么G包含k阶星Sk.1959年，Erd(ó)s和Gallai[44]证明了G包含k阶路Pk.在此基础上，1965年，Erd(ó)s和Sós[42]提出了如下猜想: Erd(ó)s-Sós猜想设G是一个n阶图.若G的边数e(G)＞n(k-2)/2，则G包含所有的k阶树. 若δ(G)≤k-2但G至少有一半顶点的度至少为k-1，G能否包含所有的k阶树？Loebl猜想若G至少有一半顶点的度至少为n/2-1，则G包含所有的n/2阶树.Komlós和Sós把这个猜想推广到一般的k。 这两个猜想现在仍然没有被解决.在Bondy和Murty的著作《图论及其应用》中，Erd(ó)s-Sós猜想被列为尚未解决的问题12;在此书的第二版中，Erd(ó)s-Sós猜想被列为尚未解决的问题31，见[17，18].由此看来，要完全解决Erd(ó)s-Sós猜想是非常困难的.在[70]中，Komlós和Simonovits指出Loebl-Komlós-Sós猜想并不比Erd(ó)s-Sós猜想简单. 在第二章，对Erd(ó)s-Sós猜想进行了研究.在2.1节，我们利用G中任意两个不相邻的顶点没有公共的非邻点，证明了若G的独立数为2，则Erd(ó)s-Sós猜想成立.这个结果改进了Li，Liu和Wang在文章[75]中的结果.在2.2节，我们利用可平面图的拓扑性质，证明了若(G)为可平面图，则Erd(ó)s-Sós猜想成立.此外，我们证明了若G为k+5阶可平面图，则(G)包含所有的k阶树. 在第三章，对Loebl-Komlós-Sós猜想进行了研究，证明了若G的独立数为2，则Loebl-Komlós-Sós猜想成立. Chvátal[32]证明了R(Km，Tn)=(m-1)(n-1)+1，其中Tn是任意的n阶树.在第四章，利用极大可平面图的拓扑性质和连通度等性质，确定了完全图对树的平面Ramsey数. 在本论文的第二部分（第五章和第六章），我们研究两个加了某些限制条件的染色问题.图的染色理论起源于十九世纪中叶的四色问题，是图论研究的的传统领域之一.染色理论不仅具有重要的理论意义，而且具有很强的应用背景.它在组合最优化，交通流，网络设计和计算机理论等方面有着重要的应用.图的染色理论内容十分丰富，除了经典的点染色，边染色以及全染色以外，还有在此基础上添加其他约束所产生的一些特殊染色问题. 设φ为图G的一个正常的k-边染色.用Cφ(v)表示与点v相关联的边的颜色的集合，则映射ψ:v→Cφ(v)是G的一个点染色，称为由φ导出的点染色.若ψ为正常的，则称φ为G的k-邻点可区别边染色.图G的邻点可区别边色数xa(G)，为最小的整数k使得G存在k-邻点可区别边染色.若G有邻点可区别边染色，则G没有孤立边.由于G的任意一个邻点可区别边染色也为G的正常的边染色，故xa(G)≥x(G).若G有相邻的最大度点，则xa(G)≥△(G)+1. 2002年，Zhang，Liu和Wang[123]提出了邻点可区别边染色的概念并提出了如下猜想. EAVD猜想对于任意阶数至少为6的连通图G，xa(G)≤△(G)+2. 下面考虑更强的染色.设A:={1，2，...，k}表示k个颜色的集合且φ为图G的一个正常的k-边染色.我们用wφ(v)表示与点v相关联的边的颜色的加和，则映射ψ:v→wφ(v)是G的一个点染色，称为由φ导出的点染色.若ψ为正常的，则称φ为G的k-邻和可区别边染色.图G的邻和可区别边色数x∑(G)，为最小的整数k使得G存在k-邻和可区别边染色.若G有邻和可区别边染色，则G没有孤立边.由于G的任意一个邻和可区别边染色也为G的邻点可区别边染色，故x∑(G)≥xa(G). 2013年，Flandrin等人[47]研究了圈，树，完全图，完全二部图的邻和可区别边色数，并提出了如下猜想: ENSD猜想设G是一个阶数至少为3的连通图.若G≠C5，则x∑(G)≤△(G)+2.Flandrin等人[47]证明了x∑(G)≤[7△(G)-4/2].Przybylo[82]利用组合零点定理证明了x∑(G)≤2△(G)+ col(G)-1≤3△(G)，其中col(G)是图G的染色数，定义为使得G有一个每个顶点的前面只能有少于k个邻点的点排序的最小整数k.最近，Przybylo[83]给出了x∑(G)的一个渐进上界并证明了x∑(G)≤(1+o(1))△(G). 图的邻和可区别边染色和著名的1-2-3猜想有着重要的联系. Karo(n)ski，(L)uczak和Thomason[69]证明了若x(G)=3，则1-2-3猜想成立.Kalkowski，Karo(n)ski和Pfender[68]证明了每个阶数至少为3的图，都是5-边权点染色的. 在第五章，我们讨论了图的邻和可区别边染色.设G为没有孤立边的图.在5.1节，我们利用权转移的方法证明了若mad(G)＜8/3，则x∑(G)≤max{△(G)+1，7};若mad(G)＜3，则x∑(G)≤max{△(G)+2，7}.这个结果改进了Dong，Wang和Zhang在文章[37]中的结果.在5.2节，我们分析了2-退化图的结构性质，证明了若G为2-退化图，则x∑(G)≤max{△(G)+2，7}. 2005年，Zhang等人[122]把邻点可区别边染色推广到了邻点可区别全染色. 设φ为图G的一个正常的k-全染色.用Cφ(v)表示点v的颜色和所有与点v相关联的边的颜色组成的集合，则映射ψ:v→Cφ(v)是G的一个点染色，称为由φ导出的点染色.若ψ为正常的，则称φ为G的k-邻点可区别全染色.图G的邻点可区别全色数x"a(G)，为最小的整数k使得G有k-邻点可区别全染色.由于G的任意一个邻点可区别全染色也为G的正常的全染色，故x"a(G)≥x"(G).若G有相邻的最大度点，则x"a(G)≥△(G)+2.Zhang等人[122]提出了如下猜想. 在第六章，我们讨论了图的邻点可区别全染色，证明了x"a(G)≤x(G)+△(G).这个结果改进了[64]中的结果.此外，我们证明了若x(G)=3，则TAVD猜想成立.