幾乎正則圖的f-色類與gc-色類的關(guān)系.pdf

1、令C是一個(gè)顏色集.圖G的邊染色是顏色在圖G的所有邊上的一個(gè)分配.令G是一個(gè)圖，一個(gè)圖G的正常邊染色是G的邊染色使得G的每個(gè)點(diǎn)處不能有相同的顏色.一個(gè)圖G的邊覆蓋染色是G的邊染色使得每種顏色在每個(gè)點(diǎn)出至少出現(xiàn)一次.一個(gè)圖G的∫-染色和gc-染色分別是正常邊染色和邊覆蓋染色的推廣.令∫和y是兩個(gè)函數(shù)，在每個(gè)點(diǎn)v∈ V(G)處分別分配一個(gè)正整數(shù)∫(v)和一個(gè)非負(fù)整數(shù)g(v).—個(gè)圖G的∫-染色是G的邊染色使得每個(gè)點(diǎn)v∈ V(G)處最多有∫(v

2、)條邊染相同的顏色.圖G的先-染色是G的邊染色使得每種顏色出現(xiàn)在每個(gè)點(diǎn)v∈ V(G)處至少有g(shù)(r)次.清晰地，圖G有∫-邊染色當(dāng)且僅當(dāng)對(duì)任意點(diǎn)v∈ V(G)有0 g g(v)< d( v).在這篇論文中，我們總是假設(shè)對(duì)任意點(diǎn)v∈ V(G)有0< g(v)< d( v).將圖G進(jìn)行∫-染色所需要的最小的顏色數(shù)目被稱為圖G的/-染色數(shù)，記作x f(G).相對(duì)地，將圖G進(jìn)行&-染色所需要的最大的顏色數(shù)目被稱為圖G的∫-染色數(shù)，記作x'f(G

3、)。(G).當(dāng)∫=1時(shí)，∫-染色恰好是正常邊染色；當(dāng)G=1時(shí)，gc-染色的確是邊覆蓋染色.因?yàn)檎＿吶旧珕?wèn)題是NP-完備的（即使是對(duì)于立方圖來(lái)說(shuō)），所以∫-染色問(wèn)題和gc-染色問(wèn)題也是NP-完備的.1986年Hakimi和Kariv證明：任意簡(jiǎn)單圖G有xf(G)=△ f(0)或△f(G)+1,這里(此處公式省略).如果（此處公式省略）,稱G為∫-染色第一類圖，否則稱G為∫-染色第二類圖.這種確定簡(jiǎn)單圖的∫-染色數(shù)的問(wèn)題稱為∫-染色的分類

4、問(wèn)題.宋慧敏和劉桂真在2005年給出的一個(gè)結(jié)果表明：任意簡(jiǎn)單圖G有（此處公式省略）這里（此處公式省略）.如果Xg。(G)=(G),稱G為gc-染色第一類圖，否則稱G為gc-染色第二類圖.這種確定簡(jiǎn)單圖的gc-染色數(shù)的問(wèn)題稱為&-染色的分類問(wèn)題.本論文主要研究了幾乎正則圖的∫-染色的分類問(wèn)題以及/-色類與先-色類之間的關(guān)系，張霞2015年證明了對(duì)于任意的正則圖G來(lái)說(shuō)，當(dāng)G的∫-核與gc-核是相同的，并且對(duì)于/-核或&-核里的每個(gè)點(diǎn)v都有∫

5、(v)= g( v),那么在∫-色類與gc-色類之間總是有一致性的結(jié)果.然而，對(duì)于其它的圖（甚至是幾乎正則圖）來(lái)說(shuō)，在∫-色類與gc-色類之間不是總是一致的.本論文對(duì)幾乎正則圖，當(dāng)滿足∫-核與gc-核是相同的，并且對(duì)任意∫-核或fit-核里的點(diǎn)v有∫(v)= g(v)時(shí),給出了∫-色類與gc-色類之間有一致性分類結(jié)果的一些充分條件.
　　本文分為四章進(jìn)行了討論.在第一章中，介紹了研究背景以及研究意義，給出了本文中用到的基本概念與符