圖論及其應用對圖的均勻染色探究

亢琳

摘 要 對于圖論研究而言，圖的染色問題既是重點，又是熱點。本文將圍繞圖的均勻染色問題展開相關探究，先后討論了平面圖的均勻染色、2-退化圖的均勻染色以及圖的全染色等。

關鍵詞 圖論 均勻染色 全染色

中圖分類號：O157 文獻標識碼：A

1 均勻染色概述

對于圖論研究而言，圖的染色問題既是重點，又是熱點。圖的均勻染色屬于一種相對特殊的圖的染色問題，自誕生以來，在以工業(yè)生產(chǎn)的代表的諸多領域獲得了廣泛應用，在處理時間表問題、剖分問題以及承載平衡問題等方面發(fā)揮出了相當重要的作用。如進行工作安排時，同一個時間段內(nèi)所要開展的工作將會受限于操作人員的數(shù)量。上述對色類大小的約束便促進了圖的有界染色問題的提出和發(fā)展。對于圖 而言，假設 為其某個正常狀態(tài)下的頂點染色，若要求在 下，無論哪一個色類中的頂點數(shù)均不可超過，那么可將 當成是圖的一個所謂的-界染色。若想予以強化，對每兩個色類提出更高的要求，要求它們的頂點數(shù)差值必須控制在1以內(nèi)，如此一來，便形成了本文所要探討的圖的均勻染色問題。很明顯，對于圖的一個均勻染色而言，也可將其當作圖的一個[∣（） ∣/]-界染色。①

圖的均勻染色，其特殊之處在于：k-可對圖進行均勻染色，然而（k+1）-并非百分百具有這個性質(zhì)。

2 圖的均勻染色

2.1 平面圖的均勻染色

設圖屬于平面圖，人們習慣用（）來代表面的集合，在保證不會造成混淆的前提下，用表示（），并將其稱之為面，且和周界上的諸點存在關聯(lián)。所謂面 的度數(shù)（）指的是，和其存在關聯(lián)關系的邊的條數(shù)，其中，割邊將會被計算2次。如果面的邊界以一個圈的形態(tài)存在，那么該面被稱之為簡單面。在∈（）的情況下，習慣用（ ）來代表面 的閉途徑，與此同時，用（ ）來代表和面存在關聯(lián)關系的頂點集。如果b（ ）包含的各個頂點依次表示為，，…，，那么可記 =（…）。②如果平面的所有頂點均位于同一個沒有界面的邊界上，那么則被稱之為外平面圖。③

對平面圖的均勻染色進行研究時，王維凡等人針對如下問題進行了研究：當△（）賦值為5時，平面圖的邊列表染色將不涉及4-圈或者6-圈。從中可獲得相應的啟發(fā)，即對不涉及短圈的平面圖的均勻染色這一類問題予以探究。

相關定理有：（1）每個不含5-圈的平面圖均是由3-退化而來的；（2）若平面圖不含3-圈、4-圈以及5-圈，那么對于任何一個≥{4，△（）}而言，存在一個-均勻染色；（3）每個不含6-圈的平面圖均是由3-退化得到的。

2.2 2-退化圖的均勻染色

以如下定理及其證明為例。

定理：將（）的一個頂點記作，假設={，，…，}為的子集，同時符合∣（）∣≤（1≤≤），當滿足-包含-均勻染色這一條件時，便能夠得出也包含-均勻染色。④

證明：令=，同時令 = [（） ∪{}]（1≤≤），那么可得出、相等。將當作是包含的一個-均勻染色，此時色集可表示為={1，2，…，}。由于∣（）∣≤，那么將必然有這樣一種顏色，能夠使條件下的不和上述染色（即）的頂點保持相鄰關系，此時，用完成的染色，則能夠?qū)Φ漠a(chǎn)生一個延拓效果，得到下的?？紤]到∣（）∣≤，那么必然有一種以上的顏色∈{}，能夠讓條件下的不和的頂點保持相鄰關系，接下來，用完成完成的染色，則能夠?qū)Φ漠a(chǎn)生一個延拓效果，得到下的。按照上述規(guī)則進行下去，直至將所涉及的諸多頂點全部賦予一種顏色，如此一來，便能夠獲得的一個所謂的-正常染色。很明顯，對于所涉及的個頂點而言，各自所染顏色全部存在差異，如此可證明 為的一個所謂的-均勻染色。

3 圖的均勻全染色

3.1 一類Mycielski圖的均勻全色數(shù)

以如下定理及其證明為例。

定理：對+1階星而言，可以得到如下結(jié)論（（））=△（（））+1（≥2）。

證明：由于△（（））=2，那么可知（（））≥2+1。現(xiàn)在僅需要對以下問題進行驗證，即存在（（））的一個2+1-均勻全染色，并將其定義為圖：（）=（（）） ∪{}，（） = （（（））/{}）∪{∣ = 0，2，3，...，}∪{， ∣ = 0，3，4，...，}∪{}?？傻谩鳎ǎ?{，}，另外，G*中所具有的最大度點的導出圖（即[△]=）屬于一條路，如此一來，可以得出：（）=△（）=2，那么對于而言，存在一個2-均勻邊染色，假設屬于的一個2-均勻邊染色，那么在這一條件的基礎上，便可構造（）的一個點邊全染色，記為，則有：（）=（），=0，2，3，…，；（）=（），=0，3，4，…，；（）=（）= （）=（）=2+1； （）= （）； （）= （）， ∈（（））/{}。很容易得出屬于（）的一個點邊全染色，同時∈{1，2，…，2+1}，另外，∣∣=3或者4。⑤所以，可以得出屬于（）的一個2+1-均勻全染色。最終證得：（（））=△（（））+1。

3.2 一些特殊平面圖的均勻全色數(shù)

以平面圖圈為研究對象，對其點邊面均勻全染色問題予以研究。

定理：對圈（）（≥3），如果 =∣∣，那么可以得出（）=+2。

證明：對圈，假設其頂點分別是，，…，，邊分別是，，…，那么可得到 = +1（=1，2，…），同時還能得到=，外部面用表示，內(nèi)部面用表示。很明顯，對于正常染色（任意）而言，和二者在顏色方面應是差異的，如此一來，對于任何一個均勻全染色而言，僅能使其色類最多包含兩個元素，對于∪∪而言，當剔除、之后，將會剩下2個元素，所以，需種以上顏色，換而言之，（）≥+2。⑥接下來，基于為其構建+2-均勻全染色，那么有：%O（）=1，（）=2。將未經(jīng)染色的那些元素按照下面的順序進行排列：…，結(jié)合上述元素的先后順序順次使用3，4，…+2，3，4，…，+2進行染色，⑦如此一來，便可獲得的一個正常狀態(tài)下的+2-均勻全染色，也就是所謂的（）≤+2。最終證得（）=+2，證明完畢。

注釋

① 李海倫.關于圖的均勻染色理論的繼續(xù)研究[D].山東大學，2010.

② 趙金麗.關于圖的均勻染色[D].浙江師范大學，2011.

③ 趙金麗，卜月華.蛛形圖的全圖和中心圖的均勻染色[J].浙江師范大學學報（自然科學版），2011.1：42-45.

④ 傅彩霞.若干倍圖的均勻染色[J].浙江師范大學學報（自然科學版），2012.2：133-137.

⑤ 伍芳蘭，左連翠.一類特殊笛卡爾積圖的均勻染色[J].山東大學學報（理學版），2013.4：20-24.

⑥ 普昭年.若干倍圖的均勻染色[J].河西學院學報，2009.5：11-14.

⑦ 朱俊蕾.退化圖的均勻染色[J].嘉興學院學報，2010.3：31-34+50.