图的一些极值问题研究

发布时间：2018-04-26 03:17

  本文选题：色数 + 诱导子树　； 参考：《南京师范大学》2017年博士论文

【摘要】：1978年,Bollobas在他的著作《极值图论》中[3]指出,图的极值理论主要研究的是,图中的某些变量,如阶数,大小,连通度,最小度,最大度,色数,直径足够大时,图中一定出现某些结构.本文主要研究了两类极值问题:Χ-有界问题和3-一致超图的Tur(?)n数问题.令Χ(G),R(l,j)分别表示图的色数和Ramsey数.给定图G和H,若V(H)(?)V(G),且 E(H)={uv|{u,v}(?)V(H)且 uv∈E(G)},则称 H 为 G 的一个诱导子图.Gyarfas和Sumner分别独立地提出了以下猜想:对于任意的树T,存在一个函数fT(x)使得每一个色数大于fT(w(G))的图均包含T作为诱导子图,其中w(G)表示图G的团数.我们称fT(X)是一个界定函数.关于Χ-有界猜想,我们做的具体工作如下:1. Gyarfas, Szemeredi和Tuza证明了若一个图G不含三角形和长为4的圈,则G含有任一个Χ(G)个顶点的树作为诱导子图.我们推广了 Gyarfas等人的这个结果,证明了:若图G的任一个顶点至多含在k个三角形和l个长为4的圈中,且Χ(G) ≥ t + 2k + 2l,则G包含任一个t个点的树作为诱导子图.2. Gyarfas,Szemeredi 和 Tuza 证明了若 G 不含三角形,且 Χ(G) ≥ m + n,则G一定包含一个特殊的树(m,n)—单杠星图作为诱导子图.我们推广了他们的结果,证明了:如果图G中的每一个顶点至多包含在k个三角形中,并且不能够诱导出T,那么,Χ(G) m(kk + 1) + n,其中T为(m,n)-单杠星图.3. Gyarfas给出了路Pn与星图Sn的界定函数,结合这两个结果与证明方法,我们找到了(m,n)-单杠星图的两个界定函数,证明了:令m和n表示大于2的整数,T表示一个(m,n)-单杠星图.那么,Forb(T)图是Χ-有界的,并且f(x)=mx-1R(3n- 2,x)是一个界定函数.更进一步地,如果g(x)= (m-1)x-1(2n)xR(3n-2,x),并且 Χ(G)≥g(w(G)),那么,对于每一个度至少为R(2- 1,w(G))的顶点v,G能够诱导出一个(m,n)-单杠星图,并且中心点与v的距离至多为2.4. Scott从拓扑的角度证明了,对于任意半径为r的树T和正整数k,每一个色数充分大的图G,其中w(G)≤k,均能够诱导出T的一个剖分,使得每条边被至多剖分成O(14r-1(r-1)!)次.我们通过对诱导子树的结构和证明过程中的划分进行了改进,证明了:对于任意半径为r的树T和正整数k,每一个色数充分大的图G,其中w(G)≤k,均能够诱导出T的一个剖分,使得每条边被至多剖分成0(6r-2)次.令ex3(n,,kG)表示恰含n个顶点的3-一致超图中不包含kkG作为子图的最多的边数,其中,kkG表示3-一致超图G的k个不交并.并且,我们称ex3(n,kG 为kG的Tur(?)n数.2011年,Gorgol给出了简单连通图不交并的Tur(?)n数,并且给出了当k = 2与k = 3时,kP2的Tur(?)n数,这个值与定理中的下界是相同的.在本文中,我们将这些结果推广到3-一致超图中,得到了 3-一致超图的不交并的Tur(?)n数的上界与下界,并且给出当图中的顶点数很大时,能够达到下界的极图:kP2+.关于3-一致超图不交并的Tur(?)n数,我们得到的具体结果如下:5.令G表示任意一个恰含m个顶点的连通3-图,k表示任意一个正整数,n是一个满足n ≥ mk的整数.那么,ex3(n,kG) ≥ max{c1,C2},其6.令G表示任意一个恰含m个顶点的连通的3-图,k表示任意一个整数.那么,ex3(n,kG) ≤ ex3(n-(k-1)m, G) +f(n,(kk — 1)m + 1),其中同时,我们证明了,当k为2的N次幂时,可以得到一个较小的上界.7.令G表示任意一个恰含m个顶点的连通3-图,k为2的N次幂(其中N为正整数).那么,ex3(n,kG)≤ex3(n-(k-1)m,G) + (?)g(n-我们称图G = (V, E)的一个r-扩展图G+的顶点集为G的顶点集,边集为{e(?)Se:e∈G},满足|Se|=r-2,Se∩V(G)=(?),Se∩Se'=(?),其中e≠e'令P2表示恰含3个顶点的路.本文中,kP2+表示P2的3-扩展图的k个不交并.我们证明了,当n充分大时,kP2+的Tur(?)n数.8.当 n 43k-(21)/2 时,有
[Abstract]:In 1978 , Bollobas in his book , graph theory of extreme value graph , pointed out that the extreme value theory of graph mainly studied that some of the variables , such as the order , size , connectivity , minimum , maximum , chromatic number and diameter of graph , must have some structure . Gyarfas , Szemeredi and Tuza demonstrate that if a graph G does not contain a triangle and a ring with a length of 4 , G contains a tree of any of the X ( G ) vertices as an inducing sub - graph . We generalize the results of Gyarfas et al . , and prove that if any one of the vertices of FIG . G is contained in a circle of k triangles and l length 4 , and X ( G ) 鈮，

本文编号：1804249