圖論是離散數(shù)學(xué)的一個(gè)重要的分支,它在生產(chǎn)管理,軍事,交通運(yùn)輸,計(jì)算機(jī)科學(xué)與技術(shù),通信工程等領(lǐng)域都有著廣泛的應(yīng)用.1736年,Euler[14]發(fā)表的關(guān)于Konigsberg七橋問(wèn)題的論文是圖論領(lǐng)域的第一篇文章.后來(lái),一些著名的圖論問(wèn)題相繼被提出,如四色問(wèn)題和中國(guó)郵遞員問(wèn)題等等.1878年,Sylvester[98]在《自然》上的一篇論文中首次提出了“圖”這一名詞.1936年,Konig[71]出版了第一本圖論專(zhuān)著《有限圖和無(wú)限圖理論》,從此圖論成為數(shù)學(xué)的一個(gè)獨(dú)立的分支.一個(gè)圖G定義為一個(gè)二元組(V(G),E(G)),記為G=(y(G),E(G)),其中V(G)是一個(gè)非空有限集,稱(chēng)為圖G的頂點(diǎn)集；E(G)是定義在V(G)上的二元關(guān)系,稱(chēng)為圖G的邊集.本文所涉及到的圖指的均是簡(jiǎn)單有限無(wú)向圖.圖G的補(bǔ)圖用G來(lái)表示.我們分別用△(G)和δ(G)表示圖G的最大度和最小度.圖G的平均度為2|E(G)|/|V(G)|.圖G的最大平均度mad(G),為G的所有子圖的平均度的最大值.如果能將圖G畫(huà)在平面上,使得它的邊僅在端點(diǎn)處相交,則稱(chēng)G是可平面圖.本文主要研究圖的極值問(wèn)題和染色問(wèn)題.在第一章,我們介紹了本文要用到的一些基本概念和符號(hào).然后,對(duì)本文涉及到問(wèn)題的背景,進(jìn)展以及已知結(jié)果給出一個(gè)比較全面的綜述.在本論文的第一部分(第二章,第三章和第四章),我們考慮與樹(shù)的存在性相關(guān)的一些極值問(wèn)題.極值圖論是圖論研究的一個(gè)重要領(lǐng)域,它起源于1941年Turan的文章[101].在該篇文章中他得到了不包含r階完全圖Kr的n階圖的最大邊數(shù),并確定了相應(yīng)的極圖.1978年,Bollobas[15]的關(guān)于極值圖論問(wèn)題的專(zhuān)著《極值圖論》的問(wèn)世標(biāo)志著極值圖論的研究已形成相對(duì)完整的理論.1998年,Chung和Graham[31]的著作搜集了Erdos在極值圖論和圖論其他課題中提出的尚未解決的問(wèn)題,將極值圖論的研究推向了一個(gè)新的高度.樹(shù)是極小的連通圖,是一類(lèi)簡(jiǎn)單而又重要的圖.1847年,Kirchhoff為了解電網(wǎng)絡(luò)中一類(lèi)線(xiàn)性方程組而提出了樹(shù)這一概念,見(jiàn)[97].1857年,Cayley[25]在研究給定碳原子數(shù)為n的飽和碳?xì)浠衔顲nH2n+2的同分異構(gòu)體時(shí)也發(fā)現(xiàn)了樹(shù),并提出了樹(shù)的計(jì)數(shù)問(wèn)題.此后,樹(shù)在化學(xué)領(lǐng)域中發(fā)揮著日趨重要的作用.隨著計(jì)算機(jī)科學(xué)的發(fā)展,樹(shù)廣泛應(yīng)用于數(shù)據(jù)結(jié)構(gòu)中,比如二叉查找樹(shù),堆,Trie樹(shù)以及Huffman樹(shù)等等.樹(shù)是圖的連通性理論中重要的子結(jié)構(gòu),一個(gè)圖是連通的當(dāng)且僅當(dāng)其有支撐樹(shù).我們考慮的問(wèn)題是：在什么條件下,圖G包含所有的k階樹(shù)?顯然,若δ(G)≥k-1,則G包含所有的k階樹(shù).若δ(G)≥k-1,則G中的邊分布較為均勻.若不考慮G中邊的分布情況,G的平均度大于k-2,G能否包含所有的k階樹(shù)?設(shè)G為平均度大于k-2的n階圖,則△(G)≥k-1,那么G包含k階星Sk.1959年,Erdos和Gallai[44]證明了G包含k階路Pk.在此基礎(chǔ)上,1965年,Erd6s和Sos[42]提出了如下猜想：Erdos-Sos猜想設(shè)G是一個(gè)n階圖.若G的邊數(shù)e(G)n(k-2)/2,則G包含所有的k階樹(shù).若δ(G)≤k-2但G至少有一半頂點(diǎn)的度至少為k-1,G能否包含所有的k階樹(shù)?Loebl猜想若G至少有一半頂點(diǎn)的度至少為n/2-1,則G包含所有的n/2階樹(shù).Komlos和S6s把這個(gè)猜想推廣到一般的k,見(jiàn)[43].Loebl-Komlos-Sos猜想設(shè)G是一個(gè)n階圖.若G至少有n/2個(gè)頂點(diǎn)的度至少為k-1,則G包含所有的k階樹(shù).這兩個(gè)猜想現(xiàn)在仍然沒(méi)有被解決.在Bondy和Murty的著作《圖論及其應(yīng)用》中,Erdos-S6s猜想被列為尚未解決的問(wèn)題12；在此書(shū)的第二版中,Erdos-S6s猜想被列為尚未解決的問(wèn)題31,見(jiàn)[17,18].由此看來(lái),要完全解決Erd6s-S6s猜想是非常困難的.在[70]中,Komlos和Simonovits指出Loebl-Koml6s-S6s猜想并不比Erdos-S6s猜想簡(jiǎn)單.在第二章,我們對(duì)Erdos-S6s猜想進(jìn)行了研究.在2.1節(jié),我們利用G中任意兩個(gè)不相鄰的頂點(diǎn)沒(méi)有公共的非鄰點(diǎn),證明了若G的獨(dú)立數(shù)為2,則Erdos-S6s猜想成立.這個(gè)結(jié)果改進(jìn)了Li, Liu和Wang在文章[75]中的結(jié)果.在2.2節(jié),我們利用可平面圖的拓?fù)湫再|(zhì),證明了若G為可平面圖,則Erdos-S6s猜想成立.此外,我們證明了若G為k+5階可平面圖,則百包含所有的k階樹(shù).在第三章,我們對(duì)Loebl-Komlos-S6s猜想進(jìn)行了研究,證明了若G的獨(dú)立數(shù)為2,則Loebl-Komlos-S6s猜想成立.設(shè)G為n階可平面圖,由歐拉公式,我們有δ(G)≤5.Brinkmann和McKay[20]證明了若n≥12且n≠13,則存在最小度為5的n階可平面圖.在2.2節(jié)我們證明了若G為k+5階可平面圖,則G包含所有的k階樹(shù).若k≥8且k≠9,則存在最小度為5的k+4階可平面圖G.由于△(G)=k-2,因而G不包含Sk,故界k+5是緊的.對(duì)任意給定的k階樹(shù)Tk≠Sk,界k+5是否仍然是緊的?特別地,對(duì)任意給定的Tk,若可平面圖G不包含kl,界k+5是否仍然是緊的?G的最小階數(shù)使得若G不包含kl,則G包含Tk即為Kl對(duì)Tk的平面Ram-sey數(shù)PR(Kl,Tk).設(shè)G1和G2為圖,G1對(duì)G2的平面Ramsey數(shù)PR(G1,G2)為最小的正整數(shù)N使得任意N階可平面圖G,若G不包含G1,則G包含G2.Chvatal[32]證明了R(Km,Tn)=(m-1)(n-1)+1,其中Tn是任意的n階樹(shù).在第四章,我們利用極大可平面圖的拓?fù)湫再|(zhì)和連通度等性質(zhì),確定了完全圖對(duì)樹(shù)的平面Ramsey數(shù).在本論文的第二部分(第五章和第六章),我們研究?jī)蓚�(gè)加了某些限制條件的染色問(wèn)題.圖的染色理論起源于十九世紀(jì)中葉的四色問(wèn)題,是圖論研究的的傳統(tǒng)領(lǐng)域之一.染色理論不僅具有重要的理論意義,而且具有很強(qiáng)的應(yīng)用背景[67].它在組合最優(yōu)化,交通流,網(wǎng)絡(luò)設(shè)計(jì)和計(jì)算機(jī)理論等方面有著重要的應(yīng)用.圖的染色理論內(nèi)容十分豐富,除了經(jīng)典的點(diǎn)染色,邊染色以及全染色以外,還有在此基礎(chǔ)上添加其他約束所產(chǎn)生的一些特殊染色問(wèn)題.設(shè)A表示k個(gè)顏色的集合.圖G的一個(gè)k-點(diǎn)染色是從V(G)到A的一個(gè)映射φ.若G中相鄰的頂點(diǎn)染不同的顏色,則稱(chēng)φ為正常的.圖G的色數(shù)χ(G),為最小的整數(shù)k使得G有正常的k-點(diǎn)染色.對(duì)任意的圖G,有χ(G)≤△(G)+1.由Brooks定理[21]知,若G既不是奇圈又不是完全圖,則χ(G)≤△(G).圖G的一個(gè)k-邊染色是從E(G)到A的一個(gè)映射φ.若G中相鄰的邊染不同的顏色,則稱(chēng)φ為正常的.圖G的邊色數(shù)χ'(G),為最小的整數(shù)k使得G有正常的k-邊染色.由Vizing定理[103]知,△(G)≤x'(G)≤△(G)+1.圖G的一個(gè)k-全染色是從V(G)∪E(G)到A的一個(gè)映射φ.若G中相鄰的或者相關(guān)聯(lián)的兩個(gè)元素染不同的顏色,則稱(chēng)φ為正常的.圖G的全色數(shù)χ"(G),為最小的整數(shù)k使得G有正常的k-全染色.顯然,χ"(G)≥△(G)+1.Molloy和Reed[77]證明了χ"(G)≤△(G)+1026.Vizing[103]和Behzad[12]分別獨(dú)立給出了如下的全染色猜想：對(duì)任意的圖G,有χ"(G)≤△(G)+2.Vijayaditya[102]和Rosenfeld[84]分別獨(dú)立證明了△(G)≤3時(shí),全染色猜想成立；Kostochka[72,73]證明了當(dāng)△(G)=4,5時(shí),全染色猜想成立；而當(dāng)△(G)≥6時(shí)全染色猜想是否成立至今仍未得到證明.設(shè)φ是圖G的邊染色(或者是全染色),接下來(lái)我們考慮由與v相關(guān)聯(lián)的邊的顏色組成的集合或者加和(或者是由與v相關(guān)聯(lián)的邊的顏色和u的顏色組成的集合)導(dǎo)出的點(diǎn)染色問(wèn)題.設(shè)φ為圖G的一個(gè)正常的k-邊染色.我們用Cφ(v)表示與點(diǎn)v相關(guān)聯(lián)的邊的顏色的集合,則映射φ:v→Cφ(u)是G的一個(gè)點(diǎn)染色,稱(chēng)為由φ導(dǎo)出的點(diǎn)染色.若φ為正常的,則稱(chēng)φ為G的k-鄰點(diǎn)可區(qū)別邊染色.圖G的鄰點(diǎn)可區(qū)別邊色數(shù)χ'α(G),為最小的整數(shù)k使得G存在k-鄰點(diǎn)可區(qū)別邊染色.若G有鄰點(diǎn)可區(qū)別邊染色,則G沒(méi)有孤立邊.由于G的任意一個(gè)鄰點(diǎn)可區(qū)別邊染色也為G的正常的邊染色,故xa'(G)≥x'(G).若G有相鄰的最大度點(diǎn),則χ'α(G)≥△(G)+1.2002年,Zhang,Liu和Wang[123]提出了鄰點(diǎn)可區(qū)別邊染色的概念并提出了如下猜想.EAVD猜想對(duì)于任意階數(shù)至少為6的連通圖G,xa'(G)≤△(G)+2.Hatami[53]利用概率的方法證明了若△(G)1020,則xa'(G)≤△(G)+300. Akbari,Bidkhori和Nosrati[4]證明了χ'α(G)≤3△(G).Zhang,Wang和Lih[124]把這個(gè)界改進(jìn)到了5(△(G)+2)／2.Balister等人[7]證明了χ'α(G)≤△(G)+O(logx(G)).下面我們考慮更強(qiáng)的染色.設(shè)A：={1,2,...,k}表示k個(gè)顏色的集合且φ為圖G的一個(gè)正常的k-邊染色.我們用wφ(v)表示與點(diǎn)v相關(guān)聯(lián)的邊的顏色的加和,則映射φ:v→ωφ(v)是G的一個(gè)點(diǎn)染色,稱(chēng)為由φ導(dǎo)出的點(diǎn)染色.若φ為正常的,則稱(chēng)φ為G的k-鄰和可區(qū)別邊染色.圖G的鄰和可區(qū)別邊色數(shù)χ'∑(G),為最小的整數(shù)k使得G存在k-鄰和可區(qū)別邊染色.若G有鄰和可區(qū)別邊染色,則G沒(méi)有孤立邊.由于G的任意一個(gè)鄰和可區(qū)別邊染色也為G的鄰點(diǎn)可區(qū)別邊染色,故x'∑(G)≥x'a(G).2013年,Flandrin等人[47]研究了圈,樹(shù),完全圖,完全二部圖的鄰和可區(qū)別邊色數(shù),并提出了如下猜想：ENSD猜想設(shè)G是一個(gè)階數(shù)至少為3的連通圖.若G≠G5,則χ'∑(G)≤△(G)+2.Flandrin等人[47]證明了χ'∑(G)≤Przybylo[82]利用組合零點(diǎn)定理證明了x'∑(G)≤2△(G)+Col(G)-1≤3△(G),其中col(G)是圖G的染色數(shù),定義為使得G有一個(gè)每個(gè)頂點(diǎn)的前面只能有少于k個(gè)鄰點(diǎn)的點(diǎn)排序的最小整數(shù)k.最近,Przybylo[83]給出了χ'∑(G)的一個(gè)漸進(jìn)上界并證明了x'∑(G)≤(1+o(1))△(G).圖的鄰和可區(qū)別邊染色和著名的1-2-3猜想有著重要的聯(lián)系.設(shè)A：={1,2,...,k}表示k個(gè)顏色的集合,且φ為圖G的一個(gè)k-邊染色.我們用wφ(v)表示與點(diǎn)v相關(guān)聯(lián)的邊的顏色的加和,則映射φ:v→χ(v)是G的個(gè)點(diǎn)染色,稱(chēng)為由φ導(dǎo)出的點(diǎn)染色.若φ為正常的,則稱(chēng)φ為G的k-邊權(quán)點(diǎn)染色.2004年,Karonski,Luczak和Thomason[69]研究了圖的邊權(quán)點(diǎn)染色,并提出如下的猜想.1-2-3猜想每個(gè)階數(shù)至少為3的圖G,都是3-邊權(quán)點(diǎn)染色的.Karonski,Luczak和Thomason[69]證明了若χ(G)=3,則1-2-3猜想成立.Kalkowski,Karonski和Pfender[68]證明了每個(gè)階數(shù)至少為3的圖,都是5-邊權(quán)點(diǎn)染色的.在第五章,我們討論了圖的鄰和可區(qū)別邊染色.設(shè)G為沒(méi)有孤立邊的圖.在5.1節(jié),我們利用權(quán)轉(zhuǎn)移的方法證明了若mad(G)8/3,則x'∑(G)≤max{△(G)+ 1,7}；若mad(G)3,則x'∑筆(G)≤max{△(G)+2,7)這個(gè)結(jié)果改進(jìn)了Dong, Wang和Zhang在文章[37]中的結(jié)果.在5.2節(jié),我們分析了2-退化圖的結(jié)構(gòu)性質(zhì),證明了若G為2-退化圖,則x'∑(G)≤max{△(G)+2,7).2005年,Zhang等人[122]把鄰點(diǎn)可區(qū)別邊染色推廣到了鄰點(diǎn)可區(qū)別全染色.設(shè)φ為圖G的一個(gè)正常的k-全染色.我們用Cφ(v)表示點(diǎn)v的顏色和所有與點(diǎn)v相關(guān)聯(lián)的邊的顏色組成的集合,則映射φ:v→Cφ(v)是G的一個(gè)點(diǎn)染色,稱(chēng)為由φ導(dǎo)出的點(diǎn)染色.若φ為正常的,則稱(chēng)φ為G的k-鄰點(diǎn)可區(qū)別全染色.圖G的鄰點(diǎn)可區(qū)別全色數(shù)χ"α(G),為最小的整數(shù)k使得G有k-鄰點(diǎn)可區(qū)別全染色.由于G的任意一個(gè)鄰點(diǎn)可區(qū)別全染色也為G的正常的全染色,故χ"α(G)≥χ"(G).若G有相鄰的最大度點(diǎn),則χ"α(G)≥△(G)+2Zhang等人[122]提出了如下猜想.TAVD猜想設(shè)G是一個(gè)圖,則χ"α(G)≤△(G)+3.Zhang等人[122]證明了G為路,圈,扇,輪,樹(shù),完全圖,完全二部圖時(shí),TAVD猜想成立.由圖的點(diǎn)染色,邊染色和鄰點(diǎn)可區(qū)別全染色的定義知xa"(G)≤x(G)+χ'(G).由Brooks定理和Vizing定理知,xa"(G)≤△(G)+△(G)+1=2△(G)+1. Huang,Wang和Yan[64]把這個(gè)界改進(jìn)到了2△(G).在第六章,我們討論了圖的鄰點(diǎn)可區(qū)別全染色,證明了xa"(G)≤x(G)+△(G).這個(gè)結(jié)果改進(jìn)了[64]中的結(jié)果.此外,我們證明了若χ(G)=3,則TAVD猜想成立.
【學(xué)位單位】：南京大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位年份】：2015
【中圖分類(lèi)】：O157.5
【文章目錄】：
摘要
Abstract
Notations
Chapter 1 Introduction
    1.1 Notations and definitions
    1.2 Problems on extremal graph theory
        1.2.1 Erdos-Sos Conjecture and Loebl-Komlos-Sos Conjecture
        1.2.2 Planar Ramsey numbers
    1.3 Problems on graph Colorings
        1.3.1 Neighbor sum distinguishing edge colorings
        1.3.2 Adjacent vertex distinguishing total colorings
Part Ⅰ Results on extremal graph theory
    Chapter 2 On the Erdos-Sos Conjecture
        2.1 Erdos-Sos Conjecture for graphs with independence number two
            2.1.1 Motivation and results
            2.1.2 Preliminary lemmas
            2.1.3 Proof of the main result
        2.2 Erdos-Sos Conjecture for graphs whose complements are planar
            2.2.1 Motivation and results
            2.2.2 Preliminary lemmas
            2.2.3 Proof of the main result
    Chapter 3 Loebl-Komlos-Sos Conjecture for graphs with independence number two
        3.1 Motivation and results
        3.2 Proof of the main result
    Chapter4 Complete graph-tree planar Ramsey numbers
        4.1 Motivation and results
        4.2 Preliminary lemmas
3,S_n）'>        4.3 PR（K₃,S_n）
3,T_n）with △（T_n）≤n-2'>        4.4 PR（K₃,T_n）with △（T_n）≤n-2
        4.5 Existence of double-star like trees
n-2（k,l）with k+l=n-4'>            4.5.1 DS_n-2（k,l）with k+l=n-4
n-2（k,l）with k+l≤n-5 and k≥3'>            4.5.2 DS_n-2（k,l）with k+l≤n-5 and k≥3
n-2（k,l）with k+l≤n-5 and k≤2'>            4.5.3 DS_n-2（k,l）with k+l≤n-5 and k≤2
        4.6 Existence of all trees
n-2 with n-6≤△(T_n-2)≤n-δ-1'>            4.6.1 T_n-2 with n-6≤△(T_n-2)≤n-δ-1
n-2 with n≥15 and △(T_n-2)=n-7'>            4.6.2 T_n-2 with n≥15 and △(T_n-2)=n-7
n-2 with △(T_n-2)≤n-δ-1'>            4.6.3 T_n-2 with △(T_n-2)≤n-δ-1
m,T_n）with m≥4 and△（T_n）≥n-3'>        4.7 PR（k_m,T_n）with m≥4 and△（T_n）≥n-3
m,T_n）with m≥4 and△（T_n）≤n-4'>        4.8 PR（K_m,T_n）with m≥4 and△（T_n）≤n-4
Part Ⅱ Results on graph colorings
    Chapter 5 On the neighbor sum distinguishing edge colorings
        5.1 Neighbor sum distinguishing edge colorings of sparse graphs
            5.1.1 Motivation and results
            5.1.2 Preliminary lemmas
            5.1.3 Proof of the main results
        5.2 Neighbor sum distinguishing edge colorings of 2-degenerate graphs
            5.2.1 Motivation and result
            5.2.2 Preliminary lemmas
            5.2.3 Proof of the main result
    Chapter 6 Upper bound on adjacent vertex distinguishing total chromatic number
        6.1 Motivation and results
        6.2 Proof of the main result
Bibliography
Acknowledgements
Awards, Foundations and Publications

【參考文獻(xiàn)】

相關(guān)期刊論文 前5條

1 單而芳，孫良;2－退化圖的全色數(shù)[J];北京理工大學(xué)學(xué)報(bào);1995年04期

2 ;On adjacent-vertex-distinguishing total coloring of graphs[J];Science in China,Ser.A;2005年03期

3 黃丹君;王維凡;;高度平面圖的鄰點(diǎn)可區(qū)別全染色[J];中國(guó)科學(xué):數(shù)學(xué);2012年02期

4 周兵;A N OTE ON THE ERD?S-S?S CONJECTURE[J];Acta Mathematica Scientia;1984年03期

5 ;The Erd?s-Sós Conjecture for Graphs Whose Complements Contain No C_4[J];Acta Mathematicae Applicatae Sinica(English Series);2004年03期

本文編號(hào)：2852485