圖的全染色、鄰點(diǎn)可區(qū)別全染色及分?jǐn)?shù)染色.pdf

1、染色問題是圖論研究的經(jīng)典領(lǐng)域，它源自四色定理的研究，是圖論研究中一個很活躍的課題．另外染色問題在組合分析和實(shí)際生活中有著廣泛的應(yīng)用，因此各類染色問題被相繼提出并加以發(fā)展、應(yīng)用． 圖G的一個(正常)k-染色是將k種顏色分配給G的頂點(diǎn)集V(G)，使得相鄰兩頂點(diǎn)的顏色不同．定義色數(shù)為：x(G)=min{k|圖G有k-染色)．類似地，圖G的一個(正常)k-邊染色是將k種顏色分配給G的邊集E(G)，使得有公共端點(diǎn)的兩邊的顏色不同．邊色數(shù)x

2、’(G)=min{k}圖G有k-邊染色}． 圖的全染色的概念是對點(diǎn)染色和邊染色的推廣，是對圖的所有元素(頂點(diǎn)和邊)都進(jìn)行染色，使得相鄰或關(guān)聯(lián)的兩元素顏色不同．圖的全色數(shù)xT(G)=min{k|圖G有k-全染色}．全染色是圖論染色的一個傳統(tǒng)問題，由Vizing(1964)[1]和Behzad(1965)[2，3]各自獨(dú)立提出的，同時分別給出全染色猜想． 鄰點(diǎn)可區(qū)別的全染色的概念是圖的一正常的全染色且任相鄰頂點(diǎn)的色集不同，由

3、張忠輔[4]在全染色的基礎(chǔ)上提出的，并同時給出了相應(yīng)的猜想和兩個引理．用xat(G)表示圖G的鄰點(diǎn)可區(qū)別的全色數(shù)． 超圖是—般圖的一個重要推廣，超圖的染色問題也是圖的染色問題的推廣．1966年Behzad首次開始超圖染色的研究，逐漸地將染色理論引入到超圖中來．超圖的全染色的概念是圖的全染色概念的一個自然推廣．王維凡，張克民在[5]中給出了超圖全染色的概念，分為弱全染色和強(qiáng)全染色兩種．超圖H-(V. E)的弱(強(qiáng))全染色是對超圖的

4、所有元素(頂點(diǎn)和超邊)都將進(jìn)行染色，使得頂點(diǎn)是弱(強(qiáng))染色，邊是強(qiáng)邊染色，并且任意關(guān)聯(lián)的頂點(diǎn)和超邊的顏色不同．超圖的弱(強(qiáng))全色數(shù)XWT(H)=min{k超圖H有弱k-全染色}(XST(H)=min{k|超圖日有強(qiáng)k-全染色})． 圖的分?jǐn)?shù)染色的概念是從圖染色的分?jǐn)?shù)推廣的角度提出的． E．Scheinennan和D．Ullman在[6]中提出了分?jǐn)?shù)染色的概念，并指出確定一個圖的分?jǐn)?shù)色數(shù)是NP-困難的．用xf(G)表示圖G的分?jǐn)?shù)色