幾乎正則圖的f-色類與gc-色類的關系.pdf

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

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

3、)。(G).當∫=1時，∫-染色恰好是正常邊染色；當G=1時，gc-染色的確是邊覆蓋染色.因為正常邊染色問題是NP-完備的（即使是對于立方圖來說），所以∫-染色問題和gc-染色問題也是NP-完備的.1986年Hakimi和Kariv證明：任意簡單圖G有xf(G)=△ f(0)或△f(G)+1,這里(此處公式省略).如果（此處公式省略）,稱G為∫-染色第一類圖，否則稱G為∫-染色第二類圖.這種確定簡單圖的∫-染色數(shù)的問題稱為∫-染色的分類

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

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