一種帶有限制的缺陷染色的研究

【摘要】 設G是一個圖. 如果圖G的頂點能夠用k個顏色來染，通過這種染色使得它的每個頂點至多有d個染相同顏色的頂點和它相鄰，而且這樣的頂點最少為t個，那么我們稱圖G是(k，d，t)*-可染的. 在這個新定義的基礎上，本文主要給出了幾種特殊圖類的一些結果和它們的證明，諸如圈#65380;完全圖等. 另外，通過“帶有限制的缺陷染色”這個新定義提出了對平面圖“四色問題”的一點新看法，對“四色定理”的證明可能會有所幫助.

【關鍵詞】 缺陷染色;(k，d，t)*-可染的;全缺圖;平面圖;四色問題

在圖的正常染色中，每個頂點所染顏色都與其相鄰頂點不同，然而，在缺陷染色中允許圖的頂點與其相鄰頂點染有相同的顏色. 缺陷染色最早是被Cowen和Woodall[1]于1986年引入的，后來Cowen#65380;Goddard和Jesurum[2]把這種染色作進一步的研究擴展到更高級更復雜的圖類. 此外，關于缺陷染色及其相關的研究，Frick[3]#65380;Woodall[4]#65380;Jessen和Toft[5]也作出了很大的貢獻，迄今為止，有了很多有價值的結果，對此我們可以參考他們的相關文章.

下面在通常意義缺陷染色的基礎上對缺陷染色的某一項指標加以限制，比如對缺陷度為一定值的頂點的個數進行限制等，基于此想法，本文提出了“帶有限制的缺陷染色”的概念，并在此概念的基礎上對一些特殊的圖進行研究，這是本文的重點之一. 另外，提出此新定義的另一個關鍵動機是基于“四色問題”，本文利用這個新定義及推出的新定理及提出的新猜想對“四色問題”的數學證明可能會起到橋梁的作用.

一#65380;本文給出的新定義

定義1 (k，d，t)* -可染的:如果用k種顏色給圖G的頂點染色，通過這種染色使得每個頂點至多有d個相鄰頂點和它染有相同的顏色，且滿足以上要求的染色使缺陷度def(v)=d的頂點個數最少為t，那么我們稱圖G是 (k，d，t)*-可染的.

定義2 全缺圖:圖G是 (k，d，t)*-可染的，|G| = n，若t = n，那么我們稱圖G為全缺圖.

二#65380;本文關于帶有限制的缺陷染色的一些研究結果

在上述引入的關于“帶有限制的缺陷染色”的幾個新概念的基礎上，這里我們給出幾類特殊的圖(例如:完全圖#65380;圈等)關于這個新定義的一些結論和它們的證明.

定理1每一個奇圈都是 (2，1，2)*-可染的.

證明 設圖G是圈v0v1v2…vnv0，且n是偶數. 若我們用兩種顏色給G按照v0→v1→v2→vn的順序染色，并且盡量遵循正常染色的原則，那么最后vn將不得不被染成和它的兩個鄰點vn-1，v0之一相同的顏色. 因此，我們說每一個奇圈都是(2，1，2)*-可染的.

定理2 每一個偶圈都是(1，2，n)* -可染的.

證明 這個定理是顯然的.

注意 在定理2中，我們可稱每一個偶圈都是全缺圖.

定理3 每個完全圖G都是 (n-1，1，2)*-可染的，|G| = n.

證明 注意到，|G| = n的完全圖G都是n-可染的. 我們用n - 1個顏色給G的頂點按照v1→v2→……→vn的順序染色.

因為圖G的每個頂點的度都是n - 1，當我們遵循正常染色的原則用n - 1個不同的顏色染完v1→v2→…→vn-1時，不管如何染 vn，它都將和它的n - 1個鄰點之一有相同的顏色. 因此，我們得出結論:每個完全圖都是(n-1，1，2)*-可染的.

定理 4 若圖G為完全圖，|G| = n，n為偶數，那么當它是，1，n*-可染時，它才是全缺的.

證明 事實上，我們把n個頂點分為 對. 因為G是完全圖，所以不管怎么分，每一對頂點都是相鄰的. 因此如果我們用兩兩不同的顏色給每一對頂點染色，那么G就是 ，1，n*-可染的.

定理 5 每一個奇階的完全圖G(|G| = n)，當它被染色為+ 1，1，n - 1* 時，總存在一個點是被正常染色的.

證明 我們仍然用4中的染色方法去給G染色，那么我們就能得到G是+ 1，1，n - 1*-可染的.

定理 6 每一個奇階的完全圖G(|G| = n)，當且僅當它是(1，n - 1，n)*-可染的時，它是全缺圖.

證明 這個定理是顯然的.

定理 7 如果圖G是(k，1，2)*-可染的，那么圖G中一定存在這樣一條邊e，當我們收縮它時能得到G的收縮圖G′ = G#8226;e的一個正常染色.

證明 已知我們用k個顏色給G染色，使得每一個頂點v(v∈G)都滿足缺陷度def(v) ≤ 1且僅有兩個頂點的缺陷度def(v) = 1，換言之，這兩個頂點染有相同的顏色. 我們記這兩個缺陷度def(v) = 1的頂點分別為vi，vj(1 ≤ i，j≤n). 除了vi和vj以外，其他的頂點缺陷度def(v) = 0. 顯然，vi和vj是相鄰的. 因此，我們收縮邊vivj = e就得到了G的收縮圖G′ = G#8226;e的一個正常染色.

定理 8 |G| = n，如果圖G是(k，2，n)*-可染的，那么G一定有一個二因子.

證明 已知G是(k，2，n)*-可染的. 現在我們構造一個2-正則生成子圖:它由n個頂點和兩個端點染相同顏色的邊組成. 根據圖G的k-因子的定義，我們構造出來的2-正則生成子圖就是G的一個2-因子.

三#65380;關于平面圖“四色問題”的一點新想法

下面根據本文的新定義提出對平面圖“四色問題”的一點想法，它對四色定理的研究可能會有所幫助.

四色問題的起源有些模糊，但可以肯定，在1852年，蓋思里(Guthrie)把四色猜想轉告了他的老師德#8226;摩根(Augustus De Morgan)，德#8226;摩根對這個問題極其感興趣并且向數學界公布了它. 四色猜想的內容如下:

定理 1 四色猜想[6]: 平面圖都是4-可染的.

本猜想自1879年A.B.Kempe給出的第一個錯誤的證明起，一個多世紀來已有許多人宣布證明了它，但都被后人一一否定. 1976年，美國數學家肯尼思#8226;阿佩爾(Kenneth Appel)和沃爾夫岡#8226;黑肯(Wolfgang Haken)宣布了一個借助于計算機的證明. 但是，這個證明引起了廣泛爭論，原因是在他們的證明使用了1000多個機時. 至今為止，嚴格的數學證明還沒有，但也沒有“四色猜想”的反例被提出.

然而，我們退一步來看，四色猜想雖不能得到證明，但“平面圖是6頂點可染的”卻是容易證明的.

定理 2[3]每個平面圖都是6頂點可染的.

1890年，Heawood改進了這個結果，他證明了:最多用五種顏色便可以給平面圖的頂點正常染色. 這個定理名為“五色定理”.

定理3[6] 每個平面圖都是5頂點可染的.

平面圖是五可染的得到確認以后，接下來人們所想的問題就是“五色定理是否是最佳的可能呢”. 因此，就出現了上述的“四色猜想:每個平面圖都是4頂點可染的”. 一個多世紀以來，盡管權威的數學家做了很多嘗試，但四色猜想一直沒有被解決，但也沒有找到反例. 只是借助于電子計算機，證明是正確的. 對此，可以參考Bull.Amer.Math.Soc.82(1976)，711-712. 若它是正確的，則它當然是最佳可能的結果，因為確實存在著不是3頂點可染的平面圖(例如:K4是最簡單的這類圖). 關于四色猜想的詳細典故，有興趣的讀者可以參閱Ore(1967)年著作.

判斷四色猜想是否正確的問題，稱為“四色問題”[7]. 雖然，對于四色定理一直沒有嚴格的數學證明，但通過缺陷染色的提出，圍繞四色定理，諸多數學家和學者給出了許多有價值的結論，大大推動了圖的染色理論#65380;平面圖理論及四色問題的發(fā)展，相關結論可以參考相關文獻[3]. 另外，Cowen和Woodall在沒有利用計算機確認的“四色定理”的前提下，他們還證明了如下的結果:

定理 4[8]每一個平面圖都是(4，1)*-可染的，并且頂點的度小于等于4的是被正常染色的.

根據上述定理4以及本文提出的新定義“帶有限制的缺陷染色”，本文給出了如下定理.

定理 5 每個平面圖都是(4，1，2t)*-可染的.

證明 由定理4知，平面圖都是(4，1)*-可染的. 我們說缺陷度def(v) = 1的頂點與同它染相同的顏色的頂點一定是相鄰的，且這個頂點的缺陷度也為1. 因此，可以說平面圖都是(4，1，2t)*-可染的，也就是說，缺陷度def(v) = 1的頂點的數目一定是偶數.

如果我們能在定理5的基礎上，對t的取值范圍作進一步的討論. 首先找到它的上界和下界，然后逐步縮小t的范圍，如果能證出下面的猜想，那么我們再根據二中的定理7便可得到四色定理.

猜想 每一個平面圖都是(4，1，2)*-可染的.

在本文新定義(k，d，t)*-可染的基礎上，我們期望能證出這個猜想. 如果能夠不用計算機而證出四色定理，這將是一個劃時代的進步，這也是本文展開研究的動機之一.

【參考文獻】

[1] T.Jensen and B.Toft， \extit{ Graph Coloring Problem}， John Wiley and Sons， 1995.

[2] D.R.Woodall. \extit{List colorings of graphs } inJ.W.P.Hirschfeld， ed， Surveys in combinatorics，2001， London Math .Soc. Lecture Note Series 288， Cambridge University Press， 2001，269-301.

[3] Cowen， L.J.， Cowen， R.H. and Woodall， D.R. (1986) Defective colorings of graphs in surfaces:partitions into subgraphs of bounded valency， \extit{J. Graph Theory} 10 187-195.

[4] Frick，M. (1993)， \extit{A survey of (m，k)-colorings}. In J. Gimbel， J.W.Kennedy， and L.V. Quintas(editors) Quo Vadis， Graph Theory， Annals of Descrete Mathematics 55 45-48， Elsevier Science Publishers.

[5] Woodall， D.R. (1990) \extit{Improper Colourings of Graphs， In R.J. Wilson(editors)， Graph Colourings， Longman Scientific and Technical.

[6] 邦迪，U.S.A 默蒂，圖論及其應用，科學出版社，1987年. [7] K. Appel and W. Haken， \extit{Every planar map is four colorable}: Part I， Discharging， Illinois J.Math. 21 (1997)， 429-490.

[8] P.Franlin， \extit{A six-color problem}， J.Math. Phys. 13(1934)， 363-369.

注:“本文中所涉及到的圖表#65380;注解#65380;公式等內容請以PDF格式閱讀原文#65377;”