【摘要】：圖染色理論和極值圖論是圖論中非常重要的兩個(gè)研究課題,在計(jì)算機(jī)科學(xué)、信息安全以及模式匹配等領(lǐng)域有著廣泛的應(yīng)用。在本文中,我們主要討論了以下幾類(lèi)圖染色問(wèn)題以及3-一致超圖中彩色匹配的Turan類(lèi)問(wèn)題。給定一個(gè)圖G =(V,E)和圖G的一個(gè)正常全染色Φ:V ∪ E →{1,2,...,k}。以mΦ(v)表示點(diǎn)v及其關(guān)聯(lián)邊上顏色的和值,即mΦ(v)=Φ(v)+∑uv∈EΦ(uv),我們稱(chēng)mΦ(v)為點(diǎn)v在染色Φ下的導(dǎo)出顏色和。如果mΦ(u)≠mΦ(v)對(duì)圖G中任意一條邊uv都成立,則稱(chēng)正常全染色Φ為圖G的一個(gè)鄰和可區(qū)別全染色。使得圖G存在一個(gè)鄰和可區(qū)別全染色的最小整數(shù)k稱(chēng)為圖G的鄰和可區(qū)別全色數(shù),記為χ"∑(G)。關(guān)于鄰和可區(qū)別全染色,Pilsniak等人猜想對(duì)于任意至少包含兩個(gè)點(diǎn)的連通圖G,其鄰和可區(qū)別全色數(shù)至多是△(G)+3。記col(G)為滿(mǎn)足下面條件的最小整數(shù)k:存在圖G的一個(gè)點(diǎn)排序,使得每個(gè)點(diǎn)至多有k—1個(gè)鄰點(diǎn)位于該點(diǎn)之前。在本文中,我們考慮的是列表鄰和可區(qū)別全染色,其相關(guān)概念的定義如下。令L = {Lx|x ∈ V ∪E}是一個(gè)列表集,如果存在一個(gè)鄰和可區(qū)別全染色Φ:V∪E→∪x∈V ∪E Lx 滿(mǎn)足對(duì)任意的x ∈ V ∪ E,都有Φ(x)∈Lx,則稱(chēng)Φ為在列表集L下的鄰和可區(qū)別全染色。如果對(duì)于任意的列表集L= {Lx丨x ∈ V∪E},只要丨Lx丨≥ k對(duì)所有的x ∈ V∪E成立,都存在圖G的一個(gè)在列表集L下的鄰和可區(qū)別全染色,則稱(chēng)圖G是k-鄰和可區(qū)別全可選的。使得圖G是k-鄰和可區(qū)別全可選的最小整數(shù)k稱(chēng)為圖G的鄰和可區(qū)別全選擇數(shù),記為ch"∑(G)。在第二章,我們結(jié)合組合零點(diǎn)定理與圖的一些結(jié)構(gòu)性質(zhì)對(duì)列表鄰和可區(qū)別全染色進(jìn)行了研究,并證明任意的圖G都滿(mǎn)足ch"∑(G)≤ △(G)+ 2col(G)—2,并且當(dāng)圖G不是森林且△(G)≥4時(shí),圖G滿(mǎn)足ch"∑(G)≤ △(G)+ 2col(G)—3。另外,對(duì)于最大度為3的圖G,我們還證明ch"∑(G)≤ 7,并且當(dāng)mad(G)20/7時(shí),ch"∑(G)≤6。假設(shè)Φ:E→{1,2,...,k}是圖G的一個(gè)正常邊染色。以CΦ(v)表示點(diǎn)v關(guān)聯(lián)邊上的顏色構(gòu)成的集合,即CΦ(v)={Φ(uv| uv ∈E},我們稱(chēng)CΦ(v)為點(diǎn)v在染色Φ下的導(dǎo)出顏色集。如果圖G中任何一條邊uv都滿(mǎn)足CΦ(≠ CΦ(v),則稱(chēng)正常邊染色Φ是圖G的一個(gè)鄰點(diǎn)可區(qū)別邊染色。使得圖G存在一個(gè)鄰點(diǎn)可區(qū)別邊染色的最小整數(shù)k稱(chēng)為圖G的鄰點(diǎn)可區(qū)別邊色數(shù),記為χ'a(G)。這一概念是由Zhang等人于2002年提出的。他們猜想對(duì)任意至少包含6個(gè)點(diǎn)的連通圖G,其鄰點(diǎn)可區(qū)別邊色數(shù)不超過(guò)△(G)+2。我們稱(chēng)一個(gè)圖為正規(guī)圖,如果該圖不含孤立邊。在第三章,我們結(jié)合組合零點(diǎn)定理和充放電技術(shù)研究了平面圖的列表鄰點(diǎn)可區(qū)別邊染色,并證明任意的正規(guī)平面圖G都滿(mǎn)足其中ch'a(G)表示圖G的鄰點(diǎn)可區(qū)別邊選擇數(shù)。與鄰和可區(qū)別全染色的定義類(lèi)似,我們定義圖G的鄰和可區(qū)別邊染色以及鄰和可區(qū)別邊色數(shù)χ'∑(G),其中點(diǎn)v在正常邊染色Φ下的導(dǎo)出顏色和mΦ(v)定義為∑uv∈EΦ(uv)。不難看出,一個(gè)圖G的鄰和可區(qū)別邊染色一定是該圖的鄰點(diǎn)可區(qū)別邊染色,因此χ'a(G≤ χ'∑(G)。關(guān)于鄰和可區(qū)別邊染色,Flandrin等人猜想除長(zhǎng)度為5的圈之外,任意的連通正規(guī)圖G的鄰和可區(qū)別邊色數(shù)至多是△(G)+2。這一猜想推廣了 Zhang等人提出的鄰點(diǎn)可區(qū)別邊染色猜想。在第三章,我們對(duì)平面圖的列表鄰和可區(qū)別邊染色進(jìn)行了研究,并證明任意的正規(guī)平面圖G都滿(mǎn)足其中ch'∑(G)是圖G的鄰和可區(qū)別邊選擇數(shù)。圖G的一個(gè)正常邊染色Φ稱(chēng)為圖G的r-無(wú)圈邊染色,如果圖G中的每一個(gè)圈C都至少包含min{|C|,r}種顏色。使得圖G存在一個(gè)r-無(wú)圈邊染色的最小顏色數(shù)稱(chēng)為圖G的r-無(wú)圈邊色數(shù),記為A'r(G)。在2005年,Greenhill等人證明對(duì)于r≥4,有A'r(d)=Θ(d「r/2」)成立,其中A'r(d):=max{A'r(G)| △(G)= d}。他們給出的A'r(d)的上界為「2 5r+4/6(r+2)」△「r/2」。在第四章,我們用熵壓縮方法對(duì)r ≥ 4時(shí)的r-無(wú)圈邊染色進(jìn)行了研究,并證明任意圖G的r-無(wú)圈邊色數(shù)不超過(guò)2△+「r/2」+O(△r+1/3),并且當(dāng)r是偶數(shù)時(shí),任意圖G的r-無(wú)圈邊色數(shù)不超過(guò)△「r/2」+O(△r+1/3)。對(duì)于r是偶數(shù)的情況,我們給出的r-無(wú)圈邊色數(shù)的上界是漸進(jìn)最優(yōu)的。另外,我們還研究了大圍長(zhǎng)圖的r-無(wú)圈邊色數(shù),并證明任意圍長(zhǎng)至少是2r-1的圖G都滿(mǎn)足A'r(G)≤(9r-7)△ + 10r-12。以上這些結(jié)果都大大改進(jìn)了之前的結(jié)果。假設(shè)H={H1,H2,...,Ht+1}是一族頂點(diǎn)集相同的k-一致超圖,如果M是一個(gè)匹配且至多包含每個(gè)Hi(i ∈[t+1])中的一條邊,則稱(chēng)M為H的一個(gè)彩色匹配。以exk(n,t)表示頂點(diǎn)個(gè)數(shù)為n且至多含有t條獨(dú)立邊(即兩兩互不相交的邊)的k-一致超圖所能具有的最大邊數(shù)。確定exk(n,t)的值是一個(gè)非常重要的Turan類(lèi)問(wèn)題。在1965年,Erdos猜想exk(n,t)= max{(k(t+1)-1 k),(n k)-(n-t k)}。最近,Aharoni 和 Howard 考慮了彩色匹配的Turan類(lèi)問(wèn)題,并猜想如果每個(gè)Hi(i∈[t + 1])的頂點(diǎn)數(shù)為n且都至少包含exk(n,t)+ 1條邊,則H含有一個(gè)大小為t+ 1的彩色匹配。在第五章,我們討論了該猜想在k= 3時(shí)的情形,并證明當(dāng)n ≥ 3.9t+ 10時(shí),該猜想成立。
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2018
【分類(lèi)號(hào)】：O157.5

【參考文獻(xiàn)】

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

1 Ai Jun DONG;Guang Hui WANG;;Neighbor Sum Distinguishing Total Colorings of Graphs with Bounded Maximum Average Degree[J];Acta Mathematica Sinica(English Series);2014年04期

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

，

本文編號(hào)：2652877