圖的鄰點可區(qū)別全染色和有全色子圖限制的染色問題.pdf

1、染色問題是圖論研究的經(jīng)典領(lǐng)域,它源自于四色定理的研究,是圖論研究中一個很活躍的課題.隨著染色問題在現(xiàn)實中被廣泛應(yīng)用,各類染色問題被相繼提出并加以發(fā)展、應(yīng)用. 圖G的一個(正常)к-染色是將к種染色分配給G的頂點集V(G),使得相鄰兩頂點的顏色不同.定義色數(shù)為:X(G)=min{к|圖G有к-染色}.類似的,圖G的一個(正常)к-邊染色是將к種染色分配給G的邊集E(G),使得有公共端點的兩邊的顏色不同.邊色數(shù)X<'>(G)=min

2、{к|圖G有尼к-邊染色). 全染色的概念是對點染色和邊染色的推廣,是圖論染色的一個傳統(tǒng)問題,由Vizing(1964)<'[24]>和Behzacl(1965)<'[25,26]>各自獨立提出的.圖的全染色是對圖的點,邊進行染色.使得相鄰或相關(guān)聯(lián)的兩元素染色不同.圖的全色數(shù)XT(G)=min{к|圖G有一個к-全染色}.在全染色的基礎(chǔ)上,張忠輔提出了鄰點可區(qū)別的全染色的概念并給出了相應(yīng)的猜想和兩個引理. 張忠輔定義的鄰

3、點可區(qū)別的全染色如下:設(shè)G(V,E)為階不小于2的簡單連通圖,к為正整數(shù),令映射f:V(G)UE(G)→{1,2,…,к).對任意u∈V(G),如果(1)對任意uu,uw∈E(G),u≠w,有f(uu)≠f(uw).(2)對任意眥,uu∈ E(G)有f(u)≠f(u)≠f(u)≠(uu)≠f(u).則稱f為圖G的一個к-全染色,簡記為к-TC.若還滿足(3)對任意uu∈E(G),c(u)≠C(u),其中C(u)={f(u))u(f(uu

4、)|uu ∈E(G)).那么稱廠為圖G的一個к-鄰點可區(qū)別全染色,簡記為к-AVDTC.圖G的全色數(shù)XT(G)(或記為X″(G))=min{k|圖G有κ-全染色}.圖G的鄰點可區(qū)別的全色數(shù)X<,a>t(G)=min{k}圖G有κ-AVDTC}.張忠輔給出了關(guān)于鄰點可區(qū)別全染色的兩個引理:對任意階為n(n≥2)的簡單連通圖G,鄰點可區(qū)別全色數(shù)X<,at>(G)存在,并且X<,at>(G)≥△(G)+1.若圖G(V, E)有兩個相鄰的最大度

5、點,則有X<,at>(G)≥a(a)+2.張忠輔在文獻[4]中給出了鄰點可區(qū)別全色數(shù)猜想:對任意階為n(n≥2)的簡單連通圖G,有X<,at>(G)≤△(G)+3. 確定一任意給定圖的鄰點可區(qū)別全色數(shù)是NP-困難的.目前關(guān)于路,圈,完全圖,完全二部圖,星,扇,輪,樹等特殊圖的鄰點可區(qū)別全色數(shù)已給出.另外上述特殊圖的Mycielski圖,聯(lián)圖和乘積圖的鄰點可區(qū)別全色數(shù)已有一些結(jié)果.同時,Petersen圖,Heawood圖,Tho

6、massen圖的鄰點可區(qū)分全色數(shù)也已得到結(jié)果. 1880年,邊染色的概念被提出,在邊染色問題的研究巾有著名的四色定理.1964年,Vizing得出一個重要的定理即對任意的簡單圖G,有△(G)≤X＇(G)≤△(G)+1. 1974年,R.P.Gupta對邊覆蓋染色進行了研究.圖G的邊覆蓋染色是對圖G的所有邊進行染色使得每種顏色在每個頂點上至少出現(xiàn)一次.滿足圖G有一個k-邊覆蓋染色的最人正整數(shù)k稱為圖G的邊覆蓋色數(shù),記為X＇

7、<,c>(G).同年,Cupta證明了對任意的簡單圖G,有δ(G)-1≤X＇<,c>(G)≤δ(G). 若X＇<,c>=δ(G),則稱G是第一類的.若X＇<,c>(G)=δ(G)-1,則稱G是第二類的.劉桂珍老師及苗連英,宋惠敏等對圖的邊覆蓋染色進行了進一步的研究并2006年,孫磊老師受邊覆蓋染色的啟發(fā)提出了全色極大團染色的概念.全色極大團染色是對圖G的頂點進行染色,使得G的每個極大團所有顏色均出現(xiàn).滿足圖G有一個k-全色極大團染色的最

8、大正整數(shù)k稱為圖G的全色極大團色數(shù),記為x<,maxcT>(G).顯然有x<,maxcT>(G)≤min{|H‖H為G的極大團). 本文一部分主要探討了輪,完全圖的Hajos sum的鄰點可區(qū)別全色數(shù).另外還得到了特殊圖P<'n><,n>,花G的鄰點可區(qū)別全色數(shù).另一部分討論了特定條件下全色極大團染色與邊覆蓋染色的等價性,給出了聯(lián)圖,復(fù)合圖,笛卡爾乘積圖,外平面圖的全色極大團色數(shù),并給出了K<,n>-M,C<,n>,Myciel