亢琳

摘 要 對(duì)于圖論研究而言，圖的染色問(wèn)題既是重點(diǎn)，又是熱點(diǎn)。本文將圍繞圖的均勻染色問(wèn)題展開(kāi)相關(guān)探究，先后討論了平面圖的均勻染色、2-退化圖的均勻染色以及圖的全染色等。

關(guān)鍵詞 圖論 均勻染色 全染色

中圖分類(lèi)號(hào)：O157 文獻(xiàn)標(biāo)識(shí)碼：A

1 均勻染色概述

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

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

2 圖的均勻染色

2.1 平面圖的均勻染色

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

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

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

2.2 2-退化圖的均勻染色

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

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

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

3 圖的均勻全染色

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

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

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

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

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

以平面圖圈為研究對(duì)象，對(duì)其點(diǎn)邊面均勻全染色問(wèn)題予以研究。

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

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

注釋

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

② 趙金麗.關(guān)于圖的均勻染色[D].浙江師范大學(xué)，2011.

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

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

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

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

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