本文選題：色數(shù) + 誘導(dǎo)子樹��； 參考：《南京師范大學(xué)》2017年博士論文

【摘要】：1978年,Bollobas在他的著作《極值圖論》中[3]指出,圖的極值理論主要研究的是,圖中的某些變量,如階數(shù),大小,連通度,最小度,最大度,色數(shù),直徑足夠大時,圖中一定出現(xiàn)某些結(jié)構(gòu).本文主要研究了兩類極值問題:Χ-有界問題和3-一致超圖的Tur(?)n數(shù)問題.令Χ(G),R(l,j)分別表示圖的色數(shù)和Ramsey數(shù).給定圖G和H,若V(H)(?)V(G),且 E(H)={uv|{u,v}(?)V(H)且 uv∈E(G)},則稱 H 為 G 的一個誘導(dǎo)子圖.Gyarfas和Sumner分別獨立地提出了以下猜想:對于任意的樹T,存在一個函數(shù)fT(x)使得每一個色數(shù)大于fT(w(G))的圖均包含T作為誘導(dǎo)子圖,其中w(G)表示圖G的團數(shù).我們稱fT(X)是一個界定函數(shù).關(guān)于Χ-有界猜想,我們做的具體工作如下:1. Gyarfas, Szemeredi和Tuza證明了若一個圖G不含三角形和長為4的圈,則G含有任一個Χ(G)個頂點的樹作為誘導(dǎo)子圖.我們推廣了 Gyarfas等人的這個結(jié)果,證明了:若圖G的任一個頂點至多含在k個三角形和l個長為4的圈中,且Χ(G) ≥ t + 2k + 2l,則G包含任一個t個點的樹作為誘導(dǎo)子圖.2. Gyarfas,Szemeredi 和 Tuza 證明了若 G 不含三角形,且 Χ(G) ≥ m + n,則G一定包含一個特殊的樹(m,n)—單杠星圖作為誘導(dǎo)子圖.我們推廣了他們的結(jié)果,證明了:如果圖G中的每一個頂點至多包含在k個三角形中,并且不能夠誘導(dǎo)出T,那么,Χ(G) m(kk + 1) + n,其中T為(m,n)-單杠星圖.3. Gyarfas給出了路Pn與星圖Sn的界定函數(shù),結(jié)合這兩個結(jié)果與證明方法,我們找到了(m,n)-單杠星圖的兩個界定函數(shù),證明了:令m和n表示大于2的整數(shù),T表示一個(m,n)-單杠星圖.那么,Forb(T)圖是Χ-有界的,并且f(x)=mx-1R(3n- 2,x)是一個界定函數(shù).更進一步地,如果g(x)= (m-1)x-1(2n)xR(3n-2,x),并且 Χ(G)≥g(w(G)),那么,對于每一個度至少為R(2- 1,w(G))的頂點v,G能夠誘導(dǎo)出一個(m,n)-單杠星圖,并且中心點與v的距離至多為2.4. Scott從拓撲的角度證明了,對于任意半徑為r的樹T和正整數(shù)k,每一個色數(shù)充分大的圖G,其中w(G)≤k,均能夠誘導(dǎo)出T的一個剖分,使得每條邊被至多剖分成O(14r-1(r-1)!)次.我們通過對誘導(dǎo)子樹的結(jié)構(gòu)和證明過程中的劃分進行了改進,證明了:對于任意半徑為r的樹T和正整數(shù)k,每一個色數(shù)充分大的圖G,其中w(G)≤k,均能夠誘導(dǎo)出T的一個剖分,使得每條邊被至多剖分成0(6r-2)次.令ex3(n,,kG)表示恰含n個頂點的3-一致超圖中不包含kkG作為子圖的最多的邊數(shù),其中,kkG表示3-一致超圖G的k個不交并.并且,我們稱ex3(n,kG 為kG的Tur(?)n數(shù).2011年,Gorgol給出了簡單連通圖不交并的Tur(?)n數(shù),并且給出了當(dāng)k = 2與k = 3時,kP2的Tur(?)n數(shù),這個值與定理中的下界是相同的.在本文中,我們將這些結(jié)果推廣到3-一致超圖中,得到了 3-一致超圖的不交并的Tur(?)n數(shù)的上界與下界,并且給出當(dāng)圖中的頂點數(shù)很大時,能夠達到下界的極圖:kP2+.關(guān)于3-一致超圖不交并的Tur(?)n數(shù),我們得到的具體結(jié)果如下:5.令G表示任意一個恰含m個頂點的連通3-圖,k表示任意一個正整數(shù),n是一個滿足n ≥ mk的整數(shù).那么,ex3(n,kG) ≥ max{c1,C2},其6.令G表示任意一個恰含m個頂點的連通的3-圖,k表示任意一個整數(shù).那么,ex3(n,kG) ≤ ex3(n-(k-1)m, G) +f(n,(kk — 1)m + 1),其中同時,我們證明了,當(dāng)k為2的N次冪時,可以得到一個較小的上界.7.令G表示任意一個恰含m個頂點的連通3-圖,k為2的N次冪(其中N為正整數(shù)).那么,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個不交并.我們證明了,當(dāng)n充分大時,kP2+的Tur(?)n數(shù).8.當(dāng) 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