(廣州大學(xué) 計算科技研究院, 廣東 廣州 510006)

1 引 言

圖的點著色和邊著色是圖論主要的研究方向,這些問題不僅在理論上具有重要的研究意義，在現(xiàn)實生活中也具有廣泛的應(yīng)用[1-2].在點著色和邊著色的基礎(chǔ)上，學(xué)者們又提出了全著色的概念.本文主要對圖的全著色研究進(jìn)展進(jìn)行綜述.首先給出文中采用的一些基本定義和符號，如果有未說明的，可參見文獻(xiàn)[3].

在沒有特殊聲明的情況下，本文所言之圖都指簡單無向圖.對于給定圖G，分別用V(G)和E(G)表示G的頂點集和邊集.圖G中所含的頂點數(shù)和邊數(shù)分別稱為G的階和規(guī)模.若G的規(guī)模為0，即E(G)=?，則稱G為空圖.兩個頂點u,v∈V(G) (或兩條邊e1,e2∈E(G))稱為相鄰的如果uv∈E(G) (或e1,e2具有相同的端點).G中的頂點u和邊e稱為是關(guān)聯(lián)的如果u是e的一個端點.用NG(u)表示G中與頂點u相鄰的所有頂點的集合，并把|NG(u)|稱為u的度數(shù)，記為dG(u).分別用δ(G)和Δ(G)表示G的最小度和最大度.所有頂點度數(shù)都為G的圖稱為k-正則圖，通常3-正則圖稱為立方圖.

給定圖G，若V(G)中任意兩個頂點在G中都相鄰，則稱圖G為完全圖，本文用記號Kn表示n-階完全圖.可見，完全圖是與空圖相對的另一個極端情況.如果V(G)可以被劃分成k個互不相交的子集(稱為部分)V1,V2,…,Vk, 即對于任意i,j∈{1,2,…,k},i≠j,Vi∩Vj=?且V=V1∪V2∪…∪Vk，使得任一邊e的兩個端點不在同一個子集中，那么稱G為k-部圖.如果一個k-部圖的任意兩個不屬于同一部分的頂點都相鄰，那么稱其為完全k-部圖，用K(r1,r2,…,rk)表示k個部分分別含有r1,r2,…,rk個頂點的完全k-部圖.如果一個k-部圖的每個部分所含的頂點數(shù)都相同，則稱其為等k-部圖.2-部圖也稱為偶圖(或二部圖)，一般用G[V1,V2]表示具有部分V1,V2的二部圖；特別地，用Km,n表示兩個部分分別含有m和n個頂點的完全二部圖.把K1,n稱為星，用Sn表示.

一個圖H稱為是G的子圖如果V(H)?V(G)并且E(H)?E(G).令H是G的一個子圖，如果V(H)=V(G)，那么稱H是G的生成子圖；如果對于u,v∈V(H)，u,v在G中相鄰當(dāng)且僅當(dāng)它們在圖H中相鄰，則稱H為G的導(dǎo)出子圖，或由V(H)導(dǎo)出的子圖，記為G[V(H)].令U是圖G的一個頂點子集，如果U中任意兩個頂點在G中都相鄰，那么稱U為G的一個團(tuán)；如果U中任意兩個頂點在G中都不相鄰，那么稱U為G的一個獨立集.

一個圖稱為路如果該圖的所有點和邊可以排列成一個點邊序列v1e1v2e2…vn-1en-1vn使得ei=vivi+1,i=1,2,…,n-1，并且序列中不含相同的點和相同的邊；如果在路v1e1v2e2…vn-1en-1vn的基礎(chǔ)上添加一條邊v1vn，所得之圖稱為圈.路和圈中所含的邊數(shù)稱為它們的長度.本文用Pn=v1v2…vn-1vn和Cn=v1v2…vn-1vnv1分別表示長度為n-1的路和長度為n的圈.長度為n的圈稱為n-圈，3-圈稱為三角形.不含圈的連通圖稱為樹.兩個圈稱為是相交的如果它們頂點集的交不空，兩個圈稱為是相鄰的如果它們邊集的交不空.

圖G的一個k-全著色是指從V(G)∪E(G)到顏色集{1,2,…,k}的一個映射f，滿足下面3個約束條件：

(1)對于任意u,v∈V(G)，如果u,v相鄰，則f(u)≠f(v);

(2)對于任意e1,e2∈E(G)，如果e1與e2相鄰，則f(e1)≠f(e2);

(3)對于任意u∈V(G)，e∈E(G)，如果u與e關(guān)聯(lián)，則f(u)≠f(e).

如果圖G含有一個k-全著色，那么稱G是k-可全著色的.把使得G是k-可全著色的最小的正整數(shù)k稱為G的全色數(shù)，表示為T(G).很顯然，T(G)≥Δ(G)+1.關(guān)于圖的全色數(shù)，Vizing[4]和Behzad[5-6]分別獨立提出下述猜想.

猜想1.1(全著色猜想TCC) 對任意簡單圖G，有

T(G)≤Δ(G)+2.

實際上，Vizing[4]所提的猜想是針對多重圖的，故更具一般性，他所提形式為：對于任意圖G，T(G)≤Δ(G)+μ(G)+1，其中μ(G)表示G的重數(shù)(若G是簡單圖，其重數(shù)為1).由于本文只關(guān)注簡單圖，故對多重圖全著色的研究不做過多介紹.

雖然在20世紀(jì)70年代，國內(nèi)外許多學(xué)者已經(jīng)證明了TCC對一些特殊圖類成立，但到目前為止還沒有給出其一個完整的證明，其難度可見一斑.為了解決TCC，圖論屆的學(xué)者們相繼提出了多種方法去攻克它，業(yè)已得到了許多非常漂亮的結(jié)果.目前，對于最大度不超過5的圖，已經(jīng)證明了TCC成立[7-9].對于度數(shù)大的圖，Molly等[10]利用概率方法(Lovász 局部引理)證明了當(dāng)Δ(G)足夠大時，T(G)≤Δ(G)+1026.該結(jié)論雖然具有一般性，但是與TCC相差甚遠(yuǎn)，所以用該方法并不能解決TCC.對于平面圖來說，利用放電法尋找可約的不可避免構(gòu)型的策略，已經(jīng)證明了對于最大度不為6的所有平面圖TCC成立.不過，人們還是想利用此方法把最大度為6的情況也解決，但是對于此情況，如何設(shè)計放電規(guī)則來尋找可約的不可避免集是一件非常困難的工作.

關(guān)于全著色問題的研究主要可歸為四個方面：①探討具有一定限制條件的圖的全色數(shù)；②探討基于全色數(shù)的圖的分類；③證明TCC對于平面圖成立；④圖的全著色算法和計算復(fù)雜性方面的研究.張忠輔等[11]在1992年對圖的全著色研究進(jìn)展進(jìn)行了綜述，介紹了1991年之前的和一些待發(fā)表的相關(guān)研究成果，并列出了一些當(dāng)時尚未解決的問題.1996年，Yap[12]對全著色的研究進(jìn)行了進(jìn)一步的總結(jié)，介紹了1995年之前的關(guān)于全著色的一些研究成果.2013年，Borodin在文獻(xiàn)[13](5.3節(jié))中簡短地介紹了2009年之前的平面圖全著色的研究情況.最近，Geetha等[14]又在上述綜述的基礎(chǔ)上，添加了一些近年來的關(guān)于全著色的研究成果.本文參考上述文獻(xiàn)，對全著色的研究進(jìn)行全面探討，綜述從1964年以來盡可能多的研究成果，并分析文獻(xiàn)中所使用的求解方法，為感興趣的讀者提供參考.

2 具有限制條件圖的全著色

由于一般圖的全色數(shù)很難判定，所以人們轉(zhuǎn)向研究了具有限制條件圖的全著色，包括一些特殊圖類，度數(shù)有限制的圖，運算圖等等.本節(jié)主要介紹一些滿足TCC的圖類，即全色數(shù)小于等于最大度加2的圖類，對于已經(jīng)得到全色數(shù)精確值的圖類將在第3節(jié)給予詳細(xì)介紹.

2.1 特殊圖類

下面介紹幾類滿足TCC的圖類，這些圖類不是很常見，但它們的結(jié)構(gòu)都具有一定的規(guī)律可循.

定義2.1(Unitary Cayley圖)Unitary Cayley圖是定義在環(huán)R上的圖GR，它的頂點集V(GR)=R，即R中的每個元素對應(yīng)GR中的一個頂點，邊集E(GR)={i,j∈R,i-j與R中所含的元素數(shù)互質(zhì)}[15].文獻(xiàn)[14](定理3.1)證明了TCC對于Unitary Cayley圖成立.

定理2.1[14]令G是Unitary Cayley圖，則T(G)≤Δ(G)+2.

由于Unitary Cayley圖包含完全圖和完全多部圖，所以由定理2.1也可以推出TCC對完全圖和完全多部圖成立.

定義2.2(Mock Threshold圖)對于任意n-階圖G，如果G的頂點可以排成一個序列v1,v2,…,vn使得對于任意i∈{1,2,…,n}，v1,v2,…,vi中每個頂點的度數(shù)屬于0,1,i-1,i-2中的一個，那么稱G是Mork Threshold圖.文獻(xiàn)[14](定理3.2)證明了此類圖滿足TCC.

定理2.2[14]令G是Mork Threshold圖，則T(G)≤Δ(G)+2.

為了構(gòu)建具有大的色數(shù)但是具有小的團(tuán)數(shù)的圖，1955年，Mycieski[16]引入了Mycielskian. 2003年，Lam等[17]將Mycielski圖進(jìn)行了擴展，構(gòu)造了廣義Mycielski圖并研究了此類圖的循環(huán)色數(shù).關(guān)于廣義Mycielski圖的研究有很多，作者在2017年研究了此類圖的鄰點可區(qū)別全色數(shù)[18].

2014年，Chen等[19]證明了TCC對于廣義Mycielski圖成立.

定理2.3[19]對于任意n-階圖G和任意正整數(shù)m，有T(μm(G)≤Δ(μm(G))+2；特別地，當(dāng)Δ(G)≤(n-1)/2或G是完全圖且n≥3時，有T(μm(G))=Δ(G)+1.

定義2.4(奇圖)對于正整數(shù)n，n-階奇圖On定義如下：On的每個頂點對應(yīng)含有2n-1個元素的集合的一個(n-1)-元子集，兩個頂點相鄰當(dāng)且僅當(dāng)它們對應(yīng)的子集不交.文獻(xiàn)[14]證明了TCC對于此類圖成立.

定理2.4[14]令On是n-階奇圖，則T(On)≤Δ(On)+2.

2.2 低度圖和高度圖

2.2.1 低度圖

對于低度圖，目前TCC被證明僅對最大度不超過5的圖成立，而且這些結(jié)論都是在20世紀(jì)90年代以前得到的.可以說對于一般圖的全著色，近20年來幾乎沒有太大的進(jìn)展.對于最大度不超過3的圖，1971年Rosenfeld[7]和Vijayditya[20]分別獨立地證明了TCC成立.

定理2.5[7,20]設(shè)G是最大度不超過3的圖，則T(G)≤Δ(G)+2.

證明定理2.5是全著色領(lǐng)域開創(chuàng)性的工作，其證明思路如下：

令G是最大度不超過3的連通圖，實際上只需考慮不含割邊的3-正則圖即可.因為若G含有割邊或含度數(shù)小于等于2的頂點，那么對G的頂點應(yīng)用數(shù)學(xué)歸納法，很容易證明TCC成立.對于不含割邊的3-正則圖G，給G的頂點正常4-著色，記為f.由于不含割邊的3-正則圖可以分解成邊不交的圈的并和一個完美匹配(Petersen定理[21]，見文獻(xiàn)[3]定理16.14)，所以G可被分解成邊不交的圈C1,C2,…的并和一個完美匹配F. 又因為f可以被擴展成G-F的一個4-全染色，所以在此基礎(chǔ)上，給F中的邊都著顏色5即得到G的一個5-全著色，從而證明了TCC對最大度不超過3的圖成立.

在上述工作的基礎(chǔ)上，Kostochka研究了多重圖的全色數(shù)，證明了TCC對最大度為4和5的多重圖成立.對于最大度為4的圖，Kostochka在1977年證明了下述結(jié)論.

定理2.6[8]對任意最大度為4的多重圖G，有T(G)≤6.

證明關(guān)于定理2.6的證明，只需考慮G是4-正則時的情況，這是因為任何一個最大度為Δ的圖都可以被嵌入到一個Δ-正則圖中.由于任意2n-正則多重圖，n≥1,都是2-可因子分解的[21](見文獻(xiàn)[12]引理4.7)，所以4-正則圖G可以分解成2個邊不交的2-因子F1，F(xiàn)2的并. 首先給圖G正常4-頂點著色(Brooks定理)，記為f. 容易證明f可以擴展成F1的一個正常4-全染色.對于F2中的奇圈C1,C2,…,可以在每個奇圈上取一個頂點v1,v2,…使得在f下，|f(ui)∪A(vi)∪A(ui)|≤3且v1,v2,…在F1中不形成奇圈，其中ui是vi在Ci中的鄰點，A(vi)={f(e)|e=xvi∈E(F1)}. 這樣通過給v1,v2,…重新用另外兩種色進(jìn)行正常2-著色之后，C1,C2,…中的邊就可以正常著色了，故定理得證.

關(guān)于最大度為5的圖，1978年Kostochka[22]在他的博士論文中證明了對于最大度為5的多重圖TCC成立，但是由于篇幅較長，并沒見發(fā)表.直到1996年，Kostochka[9]又給出了一個相對較短的證明.

定理2.7[9]對任意最大度為5的多重圖G，有T(G)≤7.

2.2.2 高度圖

在20世紀(jì)70年代，人們證明了TCC對于低度圖成立(最大度小于6的圖),但是后來很難再取得進(jìn)展，故到90年代前后，學(xué)者們開始研究高度圖的情況.

1987年，王建方等[23]通過設(shè)計一些變換，可以通過擴展一個(n-1)-階完全圖的全著色獲得最大度為n-2的n-階圖的一個n-全著色，從而證明了TCC對于最大度大于等于|V(G)|-2的圖G成立.

定理2.8[23]對于n-階圖G，如果Δ(G)≥n-2，則T(G)≤Δ(G)+2.

該成果引起了人們研究TCC對高度圖成立的熱情.1989年，Yap等[24]對其進(jìn)行了改進(jìn)，他們首先在一個圖的基礎(chǔ)上添加一個新的頂點，然后通過擴展新圖的邊著色來得到原圖的一個全著色.基于此方法，他們證明了TCC對于最大度大于等于|V(G)|-4的圖G成立.1992年，Yap等[25]又進(jìn)一步將上述結(jié)論改進(jìn)到|V(G)|-5.

定理2.9[25]對于n-階圖G，如果Δ(G)≥n-5，則T(G)≤Δ(G)+2.

1993年，Hilton等[26]進(jìn)一步證明了TCC對于最大度大于等于3|V(G)|/4的圖成立.

定理2.10[26]對于n-階圖G，如果Δ(G)≥3n/4，則T(G)≤Δ(G)+2.

2003年，Xie等[27]研究了階數(shù)為偶數(shù)的高度圖的全色數(shù)，證明了TCC對于滿足Δ(G)+δ(G)≥3|V(G)|/2-5/2的偶階圖G成立.另外，對于偶階正則圖，在文獻(xiàn)[28]中，Xie等證明了TCC對于滿足k≥2n/3+23/6的n-階k-正則圖G成立，其中n是偶數(shù).2009年，Xie等[29]又進(jìn)一步將此結(jié)論擴展到了一般正則圖上，得到下述定理.

定理2.11[29]對于n-階k-正則圖G，如果k≥2n/3+23/6，那么T(G)≤Δ(G)+2.

由于TCC若對于k-正則圖成立，那么TCC對于所有最大度為k的圖都成立[30]，所以上述對于正則圖成立的結(jié)論對于具有相同最大度的非正則圖也成立.這也說明，證明TCC成立只需探討正則圖即可.

2.3 全色數(shù)的若干上界

除了上述從低度圖和高度圖兩個方面研究TCC外，還有學(xué)者試圖通過放寬TCC中界的方法來研究TCC.1977年，Kostochka[8]證明了對于大部分最大度大于等于6的圖G，T(G)≤3Δ(G)/2.1985年，Bollobás等[31]通過列表邊著色的方法證明了如果一個圖的最大度足夠大時，該圖的全色數(shù)存在一個不超過2倍最大度的上界.

定理2.12[31]令常數(shù)c滿足11/6

1991年，Chetwynd等[32]研究了高密度圖的全色數(shù)的界，他們證明了如下定理.

定理2.13[32]如果一個圖G的最小度δ(G)≥3|V(G)|/4，那么T(G)≤Δ(G)+3；特別地，如果δ(G)≥5(|V(G)|+1)/6，那么T(G)≤Δ(G)+2.

1990年，Hint[33]通過研究邊色數(shù)(用′(G)表示圖G的邊色數(shù))和點色數(shù)(用(G)表示圖G的點色數(shù))與全色數(shù)之間的關(guān)系，得到了下面的上界.

定理2.14[Hind定理][33]對于任意圖G，有T(G)≤

定理2.15[33]對于任意圖G和任意正整數(shù)k≤Δ(G)，有T(G)≤′(G)+「(G)/k?+k.

文獻(xiàn)[34]中，作者改進(jìn)了Hind定理的上界，他們利用概率方法(Erdos-Lovász局部引理)證明了任意點色數(shù)為k的圖的全色數(shù)至多比其邊色數(shù)多18k1/3log1/23k.

1992年，Hind[35]又得到一個關(guān)于最大度的上界.

定理2.16[35]對于任意n-階圖G，有T(G)≤Δ(G)+2「n/Δ(G)?+1.

1992年，H?ggkrist等[36]證明了圖的全色數(shù)不超過其邊色數(shù)和一個常數(shù)的和.

定理2.17[36]對于n-階圖G若k是滿足k!>n的最小正整數(shù)，那么T(G)≤′(G)+k.

實際上，文獻(xiàn)[37]中證明了比定理2.17稍弱的一個結(jié)論(對于n-階圖G和任意正整數(shù)k. 若k!≥n，則T(G)≤′(G)+k+1). 另外，當(dāng)n和最大度都很大的時候，定理2.17的界要好于定理2.15.

文獻(xiàn)[38]中，McDiarmid等證明了另一個關(guān)于最大度的界.

定理2.18[38]對于任意圖G，則T(G)≤7Δ(G)/5+3.

1995年，Sánchez-Arroyo[39]改進(jìn)了定理2.18的結(jié)論，他證明了如下定理.

定理2.19[39]對于任意圖G，有T(G)≤′(G)+?(G)/3」+2.

定理2.20[40]對于任意n-階圖G，有

n+1≤T(G)+
2?n/2」+1≤T(G)

進(jìn)一步，他證明了當(dāng)n是任意奇數(shù)時，這些界都可達(dá).

1987年，王建方等[41]進(jìn)一步研究了圖與補圖的全色數(shù)，改進(jìn)了Cook的結(jié)論.

定理2.21[41]對于任意n-階圖G，有

n+1≤T(G)+
n≤T(G)

盡管目前已經(jīng)獲得許多全色數(shù)的上界，但是都與TCC相差甚遠(yuǎn)，所以通過逼近上界的方法來證明TCC成立似乎不太可行.

3 第一類圖和第二類圖

基于全色數(shù)，可以將圖G分成兩類.如果T(G)=Δ(G)+1，則稱G是第一類圖；如果T(G)=Δ(G)+2，則稱G是第二類圖.本節(jié)著重對這兩類圖進(jìn)行介紹.

在TCC提出的早期，學(xué)者們?yōu)榱蓑炞C其正確性，探討了一些特殊圖類的全色數(shù).對于至少含有3個頂點的樹來說，通過數(shù)學(xué)歸納法，很容易證明其全色數(shù)是Δ+1，即樹是第一類圖.對于n-圈Cn，n≥3，顯然T(Cn)≥3.當(dāng)n≡0(mod 3)時，容易給出Cn的3-全著色，所以T(Cn)=3，即n≡0(mod 3)時Cn是第一類圖.另外，由于在Cn的任意3-全著色下，連續(xù)的3條邊必著3種不同的顏色，所以n?0(mod 3)時可以推出T(Cn)=4，即n?0(mod3)時Cn是第二類圖.

3.1 完全圖和完全多部圖

1967年，Behzad等[42]精確地刻畫了完全圖和完全二部圖的全色數(shù).

定理3.1[42]對于n-階完全圖Kn，當(dāng)n是奇數(shù)時，T(Kn)=n；當(dāng)n是偶數(shù)時，T(Kn)=n+1.

證明定理3.1的證明并不復(fù)雜.當(dāng)n是奇數(shù)時，它的一個n-全著色可以通過如下規(guī)則給出.令V(Kn)={v0,v1,…,vn-1}，定義Kn的一個n-全著色f如下：對于每個i∈{0,1,2,…,n-1},令f(vi)=f(vi+jvi-j)=i+1，其中對于每個i，下標(biāo)j都取遍所有的{1,2,…,?n/2」},并且下標(biāo)取模n. 當(dāng)n是偶數(shù)時，可以加一個新的頂點并讓其連接Kn中的所有頂點，從而得到完全圖Kn+1.這樣，通過上述方法，可以得到Kn+1的一個(n+1)-全著色f1.顯然f1限制在Kn上的著色既是Kn的一個(n+1)-全著色.上述說明當(dāng)n是奇數(shù)時，T(Kn)≤n；當(dāng)n是偶數(shù)時，T(Kn)≤n+1.注意到，T(Kn)≥Δ(Kn)+1=n. 所以，當(dāng)n是奇數(shù)時，T(Kn)=n.另外，當(dāng)n是偶數(shù)時，Kn共有n個頂點，n(n-1)/2條邊.如果此時T(Kn)=n，由鴿巢原理，至少有一種顏色需要著至少「(n+1)/2?多個元素.但是當(dāng)n是偶數(shù)時，Kn中的獨立元素(包括點和邊)最多有n/2個，故矛盾！所以，此時T(Kn)=n+1.

上述通過鴿巢原理證明全色數(shù)下界是基本的證明思路，但并不是對所有圖都可行，所以在實際研究中，可以將其與其它策略相結(jié)合來進(jìn)行探索.

定理3.1說明當(dāng)n是奇數(shù)時完全圖Kn是第一類圖，否則是第二類圖.

對于一般的二部圖G，因為任意二部圖的邊色數(shù)不超過該圖的最大度(見文獻(xiàn)[3]，定理17.2)，所以有T(G)≤Δ(G)+2，即TCC對于二部圖成立.對于完全二部圖，Behzad等[42]證明了下述結(jié)論.

定理3.2[42]對于完全二部圖Km,n，有T(Km,n)=max(m,n)+1+δm,n,其中δm,n=0若m≠n,否則δm,n=1.

由定理3.2知，當(dāng)m≠n時，Km,n是第一類圖；當(dāng)n=m時，Km,n是第二類圖.Chen等[43]研究了Kn,n刪除一些邊后的圖是第一類圖的充要條件，他們證明了(n-2)-正則等二部圖Kn,n-E(J)是第一類圖當(dāng)且僅當(dāng)J含有長度為4的圈C4，其中J是Kn,n的子圖，Kn,n-E(J)表示從Kn,n中刪除屬于J中的邊.Hilton[44]證明了Kn,n-E(J)是第二類圖當(dāng)且僅當(dāng)|E(J)|+α′≤n-1，其中α′表示J中最大匹配所含的邊數(shù).2005年，Campos等[45]研究了一些具有特定結(jié)構(gòu)的二部圖是第一類圖的充分條件，包括網(wǎng)格圖，近梯形圖，k-立方體.

對于完全k-部圖，k≥3，Rosenfeld[7]在1971年研究了完全三部圖和完全等部圖的全著色，他證明了TCC對于這兩類圖成立.該結(jié)論在1989年被Yap[46]擴展到所有完全k-部圖，他通過證明TCC對含有至少|(zhì)V(G)|-Δ(G)-1個點的獨立集的圖G成立[24]，證明了TCC對所有完全k-部圖成立.

定理3.3[46]對于任意正整數(shù)k，完全k-部圖G的全色數(shù)滿足T(G)≤Δ(G)+2.

由于奇階完全圖是第一類圖，很自然聯(lián)想到：是否奇階完全多部圖也是第一類圖？1992年，Chew等[47]研究了此問題，并證明了奇階完全多部圖是第一類圖.

定理3.4[47]奇階完全k-部圖是第一類圖.

在定理3.4的證明過程中[47]，他們還證明了當(dāng)r1

關(guān)于判斷偶階完全多部圖是第一類圖的條件，直到2000年才有了一些進(jìn)展.Dong等[48]在2000年證明了對于偶階完全k-部圖K(r1,r2,…,rk)，r1≤r2≤…≤rk，如果r2≤r3-2，那么該圖是第一類圖；同時他們還證明了若K(r1,r2,…,rk)不是正則的且k=4，那么K(r1,r2,…,rk)也是第一類圖.這些定理的證明技巧大多是通過先把問題分解成若干種情況，然后再逐個攻克其中困難的情況.證明過程主要基于Hoffman等[49]提出的對頂點的著色思想：給某一部分的頂點都著相同的顏色，同時所有其它的頂點著不同的顏色.

近年來，Dalal等[50-51]利用圖合并技術(shù)[52]，研究了具有較低def(G)的完全多部圖G的全色數(shù)，其中def(G)被稱為圖G的deficiency，定義為

def(G)=∑v∈V(G)(Δ(G)-dG(v))，

可見def(G)可以用來衡量圖G與正則圖之間的相差程度.在文獻(xiàn)[50]中，Dalal研究了完全5-部圖的全色數(shù)，證明了K(r1,r2,…,r5)是第二類圖的充要條件是K(r1,r2,…,r5)的階數(shù)是偶數(shù)并且def(K(r1,r2,…,r5))小于圖中含有奇數(shù)個頂點的部分?jǐn)?shù).在文獻(xiàn)[51]中，作者給出了一個判斷偶階完全k-部圖K(r1,r2,…,rk)是第一類圖的充分條件，改進(jìn)了Dong等[48]的結(jié)論.

定理3.5[51]對于偶階完全k-部圖K(r1,r2,…,rk)，r1≤r2≤…≤rk，k>2，如果r2

在文獻(xiàn)[51]中，Dalal改進(jìn)了文獻(xiàn)[50]中的結(jié)論，他證明了偶階完全k-部圖K(r1,r2,…,rk)是第二類圖當(dāng)且僅當(dāng)def(K(r1,r2,…,rk))小于K(r1,r2,…,rk)中含有奇數(shù)個頂點的部分?jǐn)?shù).此外，一個特定形式的偶階完全k-部圖的全色數(shù)被完全刻畫：K(r,r,…,r,r+1)是第一類圖的充要條件是r≥k-2.

3.2 密集圖

對于任意n-階圖G，若n是奇數(shù)并且Δ(G)=n-1，這時G一定是第一類圖，因為任意奇階完全圖是第一類圖.為此，研究圖的分類最先的目標(biāo)是探討n是偶數(shù)并且Δ(G)=n-1的情況，關(guān)于這方面的先驅(qū)工作可以歸宿到1990年，Hilton[53]證明了下述定理.

定理3.6[53]令H是2n-階完全圖K2n的一個子圖，n≥1，則T(K2n-E(H))=2n+1的充要條件是|E(H)|+h≤n-1，其中h表示H中最大匹配(任意兩條邊都不相鄰的邊集)所含的邊數(shù).

按定理3.6中的條件，顯然K2n-E(H)是最大度為2n-1的2n-階圖.由于H具有任意性，上述條件可以作為判斷最大度為2n-1的2n-階圖是第一類圖的充要條件，即

定理3.7[12]令G是最大度為2n-1的2n-階圖，則G是第一類圖的充要條件是

1992年，Chen等[54]研究了最大度為2n-2的2n-階圖的全色數(shù)，他們證明了如下定理.

定理3.8[54]令G是最大度為2n-2的2n-階圖，則G是第二類圖的充要條件是

對于奇階圖，Yap等[55]給出了判斷最大度為2n-1的(2n+1)-階圖是第一類圖的充要條件.

定理3.9[55]令G是最大度為2n-1的(2n+1)-階圖，則G是第一類圖的充要條件是

對于給定圖G，用GΔ表示G中所有最大度頂點的導(dǎo)出子圖.2003年，Xie等[27]利用文獻(xiàn)[58]中的證明技巧，通過研究GΔ的結(jié)構(gòu)，證明了下述結(jié)論.

定理3.10[27]對于偶階圖G，G≠K2，如果GΔ是森林(點不交的樹的并)并且δ(G)+Δ(G)≥3(|V(G)|-1)/2，那么G是第一類圖.

3.3 積圖

兩個圖G和H的積圖，通常有四種類型，包括笛卡爾積G□H，直積G×H，強積GH和字典積G°H. 關(guān)于積圖全色數(shù)的研究主要集中在笛卡爾積，對后三種積圖的研究不是很多.這里統(tǒng)一給出這四種積圖的定義.

定義3.1(積圖)對于任意兩個圖G和H，它們上述四種積圖的頂點集都是V(G)×V(H)，它們的邊集分別是:

E(G□H)={(g,h)(g′,h′)|g=g′,hh′∈E(H) 或者h(yuǎn)=h′,gg′∈E(G)};

E(G×H)={(g,h)(g′,h′)|gg′∈E(G)且hh′∈E(H)}；

E(GH)=E(G□H)∪E(G×H)；

E(G°H)={(g,h)(g′,h′)|g=g′,hh′∈E(H) 或者gg′∈E(G)}.

由定義可以看出，G□H?H□G，G×H?H×G，GH?HG，但是G°H與H°G不一定同構(gòu).文獻(xiàn)[59]中，作者證明了笛卡爾積圖全色數(shù)與原圖全色數(shù)的關(guān)系.

定理3.11[59]對于任意圖G和H，如果TCC對于圖G和H成立，那么TCC對于G□H也成立.特別地，如果G和H中最大度大的圖是第一類圖，那么G□H也是第一類圖.

關(guān)于積圖的全色數(shù)研究很多，主要集中于兩個結(jié)構(gòu)簡單圖的積圖，比如路于路，圈與圈，完全圖和完全圖等等.下面對這些結(jié)論一一介紹.

Seoud研究了若干笛卡爾積圖的全色數(shù).在文獻(xiàn)[60]中，證明了對于m-階路Pm，n-階路Pn和n-圈Cn，Pm□Pn是第一類圖(對于任意m,n)，Pm□Cn是第一類圖(如果n=3或n是偶數(shù)).在文獻(xiàn)[61]中，他們證明了m-階路Pm與(n+1)-階星Sn的笛卡爾積圖是第一類圖；當(dāng)n≥3時，m-階路Cm與(n+1)-階星Sn的笛卡爾積圖是第一類圖；除了P2□C5外，Pm□Cn是第一類圖(該結(jié)論改進(jìn)了文獻(xiàn)[60]中相應(yīng)的結(jié)論)；如果n≥3并且m是偶數(shù)或者m≡0(mod 3)，那么Cm□Cn是第一類圖. Tong等[62]在2009年研究了圈和圈笛卡爾積圖的均勻全著色(任意兩種顏色著的元素數(shù)相差最多為1)，他們證明了如下定理.

定理3.12[62]對于任意n,m≥3，Cm□Cn存在等5-全著色.

定理3.12說明了Cm□Cn是第一類圖，該結(jié)論改進(jìn)了前面Cm□Cn是第一類圖的結(jié)論.

在文獻(xiàn)[63]中，Kemnitz等探討了兩個完全圖笛卡爾積圖的全色數(shù)，證明了對于m-階完全圖Km和n-階完全圖Kn，如果n是奇數(shù)且n≥m，那么Kn□Km是第一類圖；如果n和m都是偶數(shù)且n≥m≥4，n≡0(mod 4)或n≡6(mod 8)或n>m≥4，n≡2(mod 8)，那么Kn□Km是第一類圖；如果n是偶數(shù)，m是奇數(shù)，且n>(m-1)2，那么Kn□Km是第二類圖.在文獻(xiàn)[64]中，Baril等研究了積圖的可區(qū)別邊著色，證明了若干個(大于1個)完全圖Kn(n≥2)的笛卡爾積圖的鄰點可區(qū)別邊色數(shù)是最大度加1，其中一個圖G的鄰點可區(qū)別邊色數(shù)是指最小的正整數(shù)k,使得G存在一個正常邊著色滿足任意相鄰頂點具有不同的色集(出現(xiàn)在頂點關(guān)聯(lián)邊上的顏色的集合).由于圖G的任意鄰點(Δ(G)+1)-邊著色可以擴展成該圖的一個(Δ(G)+1)-全著色(只需適當(dāng)?shù)亟o每個頂點著一種不出現(xiàn)的顏色即可)，所以若干個(大于1個)完全圖Kn(n≥2)的笛卡爾積圖是第一類圖.

關(guān)于后三類積圖的全著色研究，Prnaver等[65]研究了路Pn與任意圖G的直積圖的全色數(shù).他們證明了如果圖G是第一類圖，那么TCC對于G×Pn成立；特別地，如果G的邊色數(shù)是Δ(G)，那么G×Pn是第一類圖.此外，他們還證明了圈Cm和路Pn的直積圖是第一類圖.2018年，Geetha等[66]分別研究了四種積圖的全著色，證明了對于任意偶數(shù)n≥4，Kn×Kn是第一類圖；對于任意整數(shù)n≥3,k≥2,l≥1, 如果m=3k,5l,8l，那么，Cm×Cn是第一類圖；此外，他們還證明了對于任意圖H，如果TCC對K2H(K2°H)成立，那么對于任意二部圖G，TCC對于GH(G°H)成立.

此外，還有學(xué)者研究了corona積和deleted字典積的全著色.兩個圖的G和H的corona積圖[67]，記作GH(這里為了與字典積區(qū)分，用符號‘’代替原文中的符號‘°’)，是指由一個G的拷貝和|V(G)|個H的拷貝通過將G的第i個頂點與H的第i個拷貝中的每個頂點相連邊構(gòu)成，其中1≤i≤|V(G)|.兩個圖G和H的deleted字典積圖[68]，記作Dlex(G,H)，是指具有頂點集V(G)×V(H)，邊集{(g,h)(g′,h′)|gg′∈E(G)且h≠h′, 或者h(yuǎn)h′∈E(H)且g=g′}的圖.在文獻(xiàn)[67]中，作者證明了如果TCC對于G成立，則GCn(n≥3)，GKn，GKm,n和GH(H是二部圖)都是第一類圖.實際上，早在1992年，Seoud[60]就證明了任意兩個圖的corona積圖是第一類圖.對于deleted字典積圖，Vignesh等[68]證明了如果G是二部圖，H是任意滿足TCC的圖，那么G°H也滿足TCC；如果G的邊色數(shù)是其最大度，那么對于任意至少含有3個頂點的圖H，Dlex(G,H)滿足TCC；特別地，如果G和H的邊色數(shù)都等于它們的最大度，那么Dlex(G,H)是第一類圖.最近，Vignesh等[69]又證明了如果G和H滿足TCC，那么它們的點corona積圖，邊corona積圖和鄰域corona積圖都是第一類圖.

3.4 弦圖

弦圖是一類非常重要的圖類，因為這類圖有許多非常好的算法性質(zhì).

定義3.2(弦圖)如果一個圖不含長度大于3的導(dǎo)出圈，即每個是圈的導(dǎo)出子圖都是三角形，那么稱該圖為弦圖.

3.5 立方圖

在第2章中，已經(jīng)介紹了TCC對立方圖成立.但是，討論第一類立方圖(全色數(shù)為4)的結(jié)構(gòu)還是很有意義的.目前已有很多立方圖類被刻畫.2016年，Dantas等[73]證明了對于任意整數(shù)k>1,都存在一個整數(shù)N(k)，對于所有n≥N(k)，廣義Petersen圖G(n,k)是第一類圖.該結(jié)論說明了幾乎所有的廣義Petersen圖都是第一類圖.

定義3.3(Snark)令G是不含割邊的連通立方圖，如果G不含3-邊著色，即邊色數(shù)是4(Vizing定理)，那么稱G為Snarks.

2003年，Cavicchiolic等[74]通過計算機輔助證明了階數(shù)小于30的所有snarks是第一類圖.他們還提出下列公開問題：

問題3.1[74]尋找(如果存在)階數(shù)最小的全色數(shù)是5的snark.

為了解決上述問題，2011年，Campos等[75]通過遞歸程序為三類特殊的snarks分別構(gòu)建了4-全著色，包括Flower Snarks, Goldberg Snarks和Twisted Goldberg Snarks，從而證明了這三類snarks是第一類圖.基于這些結(jié)果，他們猜想所有snarks都是第一類圖.2014年，Sasaki等[76]為尋找全色數(shù)是5的snarks，研究了幾類特殊snarks的全色數(shù)，包括Blanu?a類和一類不含四邊形的snarks，然而這些snarks也都是第一類圖.他們注意到對于cyclic-邊連通度小于4的立方圖，其全色數(shù)看似與其邊色數(shù)關(guān)系不大；同時，他們還發(fā)現(xiàn)找到的所有第二類立方圖都含有四邊形.為此，他們進(jìn)一步提出下列問題.

問題3.2[76]不含四邊形的階數(shù)最小的全色數(shù)為5的立方圖是什么？

問題3.3[76]最小的全色數(shù)是5的snark是什么？

針對上述問題，Brinkmann等[77]在2015研究了全色數(shù)是5的snarks的構(gòu)造，他們證明了對于任意不小于40的偶數(shù)n，都存在一個全色數(shù)是5的n-階snark，從而回答了上述問題3.1和問題3.3. 另外，他們用計算機搜索驗證了所有階數(shù)不超過32的圍長(最短圈的長度)為5的立方圖的全色數(shù)，結(jié)果發(fā)現(xiàn)這些圖都是第一類圖.故他們提出以下三個問題.

問題3.4[77]是否存在階數(shù)小于40的全色數(shù)是5的snark？

關(guān)于問題4，目前沒有驗證的僅是階數(shù)為36和38的snarks.

問題3.5[77]最小的全色數(shù)是5的圍長至少為5的立方圖是什么？

問題3.6[77]是否存在g使得所有圍長至少為g的立方圖都是第一類圖？

3.6 其它圖類

除了上述圖類外，還有許多其它圖類的全著色被研究.

定義3.4(聯(lián)圖)對于點不交的兩個圖G1,G2，若將圖G1中的每個頂點與圖G2中的每個頂點相連邊，則得到的新圖稱為G1與G2的聯(lián)圖，對于任意n≥3，1-階完全圖K1與n-階圈Cn的聯(lián)圖K1+Cn稱為輪圖，其中K1中的頂點稱為該輪圖的輪心.

定義3.5(theta圖)令G是最大度為3的塊，即不含割點的連通圖，如果G恰好含有兩個不相鄰的度數(shù)為3的頂點并且其余頂點的度數(shù)都為2，那么稱G為theta圖.

在文獻(xiàn)[60]中，Seoud研究了這兩類圖的全色數(shù)，得到下面的結(jié)論.

定理3.13[60]任意兩個階數(shù)不同的路的聯(lián)圖是第一類圖；任意theta圖是第一類圖.

注意，定理3.13中構(gòu)成聯(lián)圖的兩個圖要求階數(shù)不同，如果相同結(jié)果并非如此.比如P2+P2=K4，而K4是偶階完全圖，是第二類圖.

定義3.6(梯圖)令C2n=u1u2…unv1v2…vnu1是長度為2n的圈，對于每個i=1,2,…,n，如果在ui和vi之間連r(≥1)條邊，那么所得之圖稱為r重M?bius梯圖，記為M2n(r).當(dāng)r>1時，M2n(r)是多重圖.

在文獻(xiàn)[78]中，Chetwynd證明了如下定理.

定理3.14[78]對于任意n≥2,r≥1，M2n(r)是第二類圖.

定義3.7(Compound圖)兩個圖G和H的Compound圖是指對于H中的每個頂點u,取1個G的復(fù)制Gu，并在任意兩個Gv和Gw之間連一條邊(或一對邊)如果頂點v和w在H中相鄰. 顯然，不同的連邊方式會產(chǎn)生不同的圖.另外G和H的Compound圖與H和G的Compound圖不一定同構(gòu).

文獻(xiàn)[79]中，Mohan等證明了如下定理.

定理3.15[79]當(dāng)G和H都滿足TCC時，G和H的Compound圖是第一類圖.

定義3.8(線圖)一個圖G的線圖用L(G)表示，它的頂點集是G的邊集E(G)，兩個不同的頂點e1,e2∈E(G)在L(G)中相鄰當(dāng)且僅當(dāng)它們在G中有相同的端點.

Vignesh等在文獻(xiàn)[68]中研究了完全圖Kn線圖的全色數(shù)，證明了：

定理3.16[68]當(dāng)n≤4時，L(Kn)是第一類圖.

進(jìn)一步，Vignesh等[68]猜測對于任意n,L(Kn)都是第一類圖.

在文獻(xiàn)[80]中，作者探討了基于星和雙星運算圖的全色數(shù)，包括middle圖，全圖，線圖，平方圖，證明了這些圖幾乎都是第一類圖.

定義3.9(倍圖)一個圖G的倍圖用D(G)表示，它由G的兩個拷貝組成，并對于任意uv∈E(G)在它們之間添加邊(u,1)(v,2)和(v,1)(u,2)，其中(x,i)表示G中的頂點x對應(yīng)到其第i個拷貝中的頂點，i=1,2.

在文獻(xiàn)[68]中，Vignesh等證明了：

定理3.17[68]如果G滿足TCC，那么D(G)也滿足TCC；特別地，如果G是第一類圖，那么D(G)也是第一類圖.

定義3.10(唯一弦)圖G中圈C的一條弦是指G中不屬于C的一條端點都在C上的邊.圈C的一條弦稱為唯一的如果C再無其它的弦.

Machado和de Figueiredo[81-82]用兩篇文章研究了不含唯一弦和四邊形的圖的全色數(shù).他們分別證明了：

定理3.18[81-82]TCC對于不含四邊形和唯一弦的圖成立；特別地，對于非完全不含四邊形和唯一弦的圖G，當(dāng)Δ(G)≥3時，G是第一類圖.

定義3.11(k-退化圖)對于n-階圖G，如果V(G)可以被排成一個序列，令為v1,v2,…,vn，使得每個vi都與其后面最多k個頂點相鄰，k>0，那么稱G是k-退化的.

關(guān)于k-退化圖，1997年，Borodin等[83]證明了任意最大度Δ(G)≥2k2的k-退化圖G是第一類圖.2007年，Isobe等[84]改進(jìn)了Borodin的結(jié)論，他們通過引入所謂的局部著色和疊加技術(shù)，利用退化圖邊著色的Vizing定理(最大度Δ(G)≥2k的k-退化圖G的邊色數(shù)等于其最大度[85-86])和二部圖邊著色的K?nig定理(每個二部圖的邊色數(shù)等于其最大度[87])證明了：

定理3.19[84]令G是k-退化圖并且Δ(G)≥k+3，則G是第一類圖.

定義3.12(循環(huán)圖)對于正整數(shù)序列1≤d1

Khennoufa等[88]在2008年研究了此類圖的全色數(shù)，證明了此類圖的參數(shù)n,k在滿足一些限制條件時是第一類圖.

定理3.20[88]對于任意正整數(shù)p和k<5p/2滿足k≡2mod 5或者k≡3(mod 5)，每個4-正則循環(huán)圖C5p(1,k)是第一類圖；對于任意正整數(shù)p≥3和k<3p滿足k≡1(mod 3)或者k≡2(mod 3)，每個4-正則循環(huán)圖C6p(1,k)是第一類圖.

定義3.13(Sierpiński圖)對于正整數(shù)n,k及k-階完全圖Kk，Sierpiński圖S(n,k)指具有頂點集{1,2,…,k}n，兩個頂點u=(u1,u2,…,un)和v=(v1,v2,…,vn)相鄰當(dāng)且僅當(dāng)存在h∈{1,2,…,n}使得下面三條成立：(1)對于所有t=1,2,…,h-1，有ut=vt；(2)uh≠vh；(3)對于t=h+1,…,n，有ut=vh并且vt=uh.

在Sierpiński圖S(n,3)的基礎(chǔ)上，收縮S(n,3)中每一條不在三角形上的邊，所得之圖稱為Sierpiński gasket圖[89]，記作S(n)(這里為了與星圖區(qū)別，所以用符號S(n)表示).Jakovac等[90]證明了對于任意n≥2,S(n)是第一類圖；對于任意n≥1和k≥1,T(S(n,k))≤k+2；特別地，對于任意n≥1，若k≥3是奇數(shù)，則S(n,4)和S(n,k)是第一類圖.對于k≥6是偶數(shù)的情況，它們猜想S(n,k)是第二類圖.然而，三年之后，Hinz等[91]通過研究Hanoi圖的著色，構(gòu)造出了該猜想的反例，從而說明對于k≥6是偶數(shù)的情況，S(n,k)不一定全是第二類圖.Geetha等[92]研究了廣義的Sierpiński圖S(n,G)的全色數(shù)，他們證明了對于一些特定第一類圖G，比如房子圖，輪圖，圈的笛卡爾積圖等，S(n,G)是第一類圖.

本節(jié)主要介紹了一些關(guān)于第一類圖和第二類圖的結(jié)果，盡管目前有許多這方面的研究成果，都是局限于特定圖或圖類.對于一般圖，很難通過這種分類方式解決TCC.

4 平面圖的全色數(shù)

本節(jié)重點介紹平面圖全著色的研究進(jìn)展，首先給出平面圖的定義.

定義4.1(平面圖)對于圖G，如果在平面上有一種G的畫法使得任意兩條邊要么不相交要么交點是它們的公共端點，則稱G是平面圖或者可平面的，而這種畫法稱為G的一個平面嵌入.通常說平面圖G均指G的一個平面嵌入.

在平面圖著色領(lǐng)域，有一種卓越的證明技巧——放電法.該方法在圖論中的應(yīng)用已有百年的歷史，但直到1977年，Appel等[93-94]采用該方法宣布解決四色猜想后，該方法才正式得到了廣泛的關(guān)注.到目前為止，采用該方法解決的平面圖著色相關(guān)的問題數(shù)不勝數(shù)，而平面圖全著色的研究，也主要采用該技巧.關(guān)于放電法的詳細(xì)介紹，可參見文獻(xiàn)[95].

由于TCC很早就被證明對于最大度小于等于5的一般圖成立[9,22]，當(dāng)然也包括平面圖，所以關(guān)于平面圖全著色的結(jié)論，都是針對最大度大于等于6的平面圖.1987年，Borodin[96]最早研究了平面圖全著色問題，證明了TCC對于最大度大于等于11的平面圖成立；兩年后，他將最大度的下界從11減小到9[97].1995年，Jensen等[98]將最大度的下界減小到8(也見文獻(xiàn)[12]).1999年，Sanders等[99]進(jìn)一步將最大度的下界減小到7.

定理4.1[99]令G是最大度大于等于7的平面圖，則T(G)≤Δ(G)+2.

證明在文獻(xiàn)[99]中，作者首先定義了13種特殊類型的頂點，通過放電法證明了每個平面圖至少含有它們中的1種，最后證明沒有最小反例含有這些類型的點，從而產(chǎn)生矛盾.此外，如果承認(rèn)四色定理[93-94]已經(jīng)成立，定理4.1還可以證明如下[13]：

令G是一個最大度大于等于7的平面圖，那么G的邊色數(shù)是Δ(G)[100-101]，用顏色集{1,2,…,Δ(G)}對G進(jìn)行邊著色，然后擦去著顏色Δ(G)-1和Δ(G)的頂點的顏色.根據(jù)四色定理，用顏色集{Δ(G)-1,Δ(G),Δ(G)+1,Δ(G)+2}對G的頂點進(jìn)行著色.因為每條沒有著色的邊都至少有{1, 2,…,Δ(G)+1,Δ(G)+2}中兩種可選的顏色，而且沒著色的邊在圖中的導(dǎo)出子圖是路和偶圈的并，所以這些邊可以被正常著色，從而定理成立.

對于不加限制條件的平面圖，定理4.1的結(jié)果是目前最好的，因為TCC對于最大度為6的平面圖是否成立仍是公開的問題.

問題4.1[99]是否每個最大度為6的平面圖都有8-全可著色？

關(guān)于最大度為6的平面圖，盡管問題4.1還沒有被徹底解決，但是已取得了大量的成果.2007年，Wang等[102]證明了:

定理4.2[102]令G是最大度為6的平面圖，如果G不含4-圈，那么G是8-全可著色.

2009年，Shen等[103]改進(jìn)了定理4.2的結(jié)論，證明了不含4-圈的最大度為6的平面圖存在7-全著色.同年，Sun等[104]證明了不含相鄰三角形的最大度為6的平面圖存在8-全著色.2011年，Roussel[105]改進(jìn)了Sun等[104]的結(jié)論，證明了對于最大度為6的平面圖G，如果G中每個頂點v不與某個kv-圈關(guān)聯(lián)，kv∈{3, 4, 5, 6, 7, 8}，那么G存在8-全著色.在文獻(xiàn)[106]中，Li又改進(jìn)了Roussel的結(jié)論，證明了對于最大度為6的平面圖G，如果對于任意頂點v都存在一個整數(shù)kv∈{3, 4, 5, 6}使得v不與任意kv-圈關(guān)聯(lián)， 那么G存在8-全著色.2017年，作者進(jìn)一步改進(jìn)了Sun等[104]的結(jié)論，證明了：

定理4.3[107]令G是最大度為6的平面圖，如果G不含同構(gòu)于4-扇的子圖，那么G存在8-全著色，其中4-扇是1-階完全圖K1與5-階路的聯(lián)圖.

由于問題4.1很難被徹底解決，人們開始轉(zhuǎn)向研究什么樣的平面圖是第一類圖.在這方面，最早的研究還是源于Borodin[96]，他在1987年證明了最大度大于等于16的平面圖是第一類圖，隨后，最大度的下界分別被改進(jìn)到14[97]、12[108]、11[109]和10[110]，最后由Kowalik等[111]和Sun等[104]改進(jìn)到9.在文獻(xiàn)[104]中，作者還證明了不含相鄰三角形并且不含長度大于等于5的圈的平面圖是第一類圖.

定理4.4[111]令G是最大度大于等于9的平面圖，則G是第一類圖.

基于定理4.4，Kowalik等[111]提出下列問題刻畫第一類平面圖.

問題4.2[111]使得最大度大于等于k的平面圖是第一類圖的最小整數(shù)k是多少？

由于K4是最大度為3的平面圖且T(K4)=5，所以問題4.2中k應(yīng)該屬于{4,5,6,7,8,9}.基于此，Shen等[103]將上述問題改寫成下述猜想：

猜想4.1[103]最大度Δ(G)滿足4≤Δ(G)≤8的平面圖是第一類圖.

如果猜想4.1成立，那么基于定理4.4有每個最大度大于等于4的平面圖都是第一類圖.針對猜想4.1，對于最大度為6的平面圖，Zhang等[112]證明了每個最大度至少為6的不含相鄰短圈的平面圖是第一類圖，這里的短圈指3-圈和4-圈.Hou等[113]證明了最大度大于等于5的平面圖如果不含4-圈和6-圈，那么該圖是第一類圖；最大度大于等于6的平面圖如果不含5-圈和6-圈，那么該圖是第一類圖.Wu等在文獻(xiàn)[114]中證明了平面圖G如果不含弦l-圈，l=5,6，那么G有一個k-全著色，其中k=max{7,Δ(G)+1}, 這里弦l-圈指至少有一條弦的圈；注意到當(dāng)Δ(G)≥6時，k=Δ(G)+1，所以此結(jié)論改進(jìn)了Hou等[113]的結(jié)果.

最大度大于等于7的平面圖是第一類圖的充分條件包括：不含5-圈[115]；對于任意頂點v都存在一個整數(shù)kv∈{3, 4, 5, 6}使得v不與任意kv-圈關(guān)聯(lián)[116]；3-圈不與4-圈相交或者3-圈不與長度小于6的圈相鄰[117]；不含相交3-圈[118]；不含相交5-圈[119]；不含相鄰4-圈[120]；不含弦6-圈[121]；不含弦7-圈[122].

對于最大度大于等于8的平面圖，目前判斷其是第一類圖的充分條件比較多.令G是最大度為8的平面圖，則G是第一類圖的充分條件包括：G不含k-圈，k∈{5,6}[123]；對任意頂點v∈V(G), 都存在一個整數(shù)kv∈{3, 4, 5, 6, 7, 8}使得v不與任意kv-圈關(guān)聯(lián)[124]；對任意頂點v∈V(G), 都存在兩個整數(shù)kv,lv∈{3, 4, 5, 6, 7, 8}使得v不與相交的kv-圈和lv-圈關(guān)聯(lián)[125]；對任意頂點v∈V(G), 都存在兩個整數(shù)kv,lv∈{3, 4, 5, 6, 7,}使得v不與相鄰的kv-圈和lv-圈關(guān)聯(lián)[126]；G中每個7-圈至多含有兩條弦[127]；G不含相鄰的分別含有兩條弦的i-圈和j-圈，i,j∈{5, 6, 7}[128]；G不含含有兩條弦的5-圈[129]；不含相交弦4-圈[130]；每個6-圈至多含有一條弦或者任意弦6-圈不相鄰[131]；i-圈不與j-圈相鄰，3≤i≤j≤5[132]；任意v∈V(G)不關(guān)聯(lián)弦6-圈或者弦7-圈或者2-弦5-圈[133]；每個頂點v∈V(G)關(guān)聯(lián)至多dG(v)-2?dG(v)/5」個三角形[134].

在文獻(xiàn)[135]中，Wang等研究了具有較小最大度的平面圖的全著色.令G是最大度為Δ圍長為g的平面圖，且存在整數(shù)t>g使得G不含長度屬于{g+1,…,t}的圈.他們證明了如果(Δ,g,t)∈{(5,4,6),(4,4,17)}，或者Δ=3且(g,t)∈{(5,13),(6,11),(7,11),(8,10),(9,10)}且每個頂點至多關(guān)聯(lián)一個長度為g的圈，那么G是第一類圖.

上述這些充分條件，有些后者是前者的擴展和改進(jìn)，但大多都是獨立的.目前盡管得到了眾多的充分條件，但是仍然沒有給出第一類平面圖的完全刻畫，故要想解決猜想4.1，仍有大量的工作需要做.下面介紹外平面圖和一些類似平面圖的圖類的全著色研究情況.

定義4.2(外平面圖)如果一個平面圖存在一種平面嵌入使得所有頂點均位于一個面(外部面)的邊界上，那么稱該平面圖為外平面圖.

文獻(xiàn)[136]研究了外平面圖的鄰點可區(qū)別全著色，所得結(jié)論可以自然推廣到全著色上.

定理4.5[136]令G是外平面圖，如果Δ(G)≥4，那么T(G)≤Δ(G)+2；特別地，若G不含相鄰的最大度點，那么T(G)=Δ(G)+1.

定義4.3(1-toroidal圖)如果一個圖可以畫到圓環(huán)面上使得每條邊與其它邊相交至多一次，那么該圖稱為1-toroidal圖.

Wang[137]研究了此類圖的全色數(shù)，證明了:

定理4.6[137]令G是最大度大于等于11的1-totoidal圖，如果G不含相鄰三角形，那么T(G)≤Δ(G)+2.

定義4.4(1-平面圖)如果一個圖有一個平面嵌入使得每條邊至多與其它一條邊交叉(不在端點處相交)，那么該圖稱為1-平面圖.

Zhang等[138]研究了此類圖的列表全著色，證明了對于任意1-平面圖G，如果Δ(G)≥16，則G的列表全色數(shù)小于等于Δ(G)+2；如果Δ(G)≥21，則G的列表全色數(shù)等于Δ(G)+1.這也說明了1-平面圖的全色數(shù)對上述結(jié)論也成立.在文獻(xiàn)[139]中，Zhang等又進(jìn)一步證明了:

定理4.7[139]令G是1-平面圖，如果Δ(G)≥13，那么T(G)≤Δ(G)+2.

在文獻(xiàn)[140]中，Czap研究了1-平面圖G全色數(shù)的上界.證明了如果Δ(G)≥10,則T(G)≤Δ(G)+3；如果Δ(G)≥10且G的點色數(shù)小于等于4，那么T(G)≤Δ(G)+2；對于不含相鄰三角形的1-平面圖G，如果Δ(G)≥8；則T(G)≤Δ(G)+3;如果G的點色數(shù)小于等于4，那么T(G)≤Δ(G)+2.

5 計算復(fù)雜性

6 結(jié)束語

本文對全著色的研究進(jìn)展進(jìn)行了全面的綜述，由所闡述的結(jié)果來看，除了一些特殊的情況外，TCC仍是公開的難題，甚至對于平面圖，TCC也沒有被徹底解決.

1992年，張忠輔等[11]在總結(jié)前人成果的基礎(chǔ)上提出了一些問題并歸納了當(dāng)時研究全著色的一些方法，包括窮舉法，轉(zhuǎn)換成邊著色的方法，轉(zhuǎn)換成全圖的方法，匹配理論和其它的一些構(gòu)造方法.經(jīng)過多年的研究，盡管又產(chǎn)生了一些新的方法，但是也都是些基于組合的方法，而且大部分只適用于特殊的圖類，所以擴展性不強.對于平面圖來說，利用放電策略尋找可約的不可避免集的方法，已經(jīng)證明了TCC對幾乎所有的平面圖成立，只有最大度為6且含4-圈的特殊情況沒有解決.作者相信利用放電法能夠最終解決這種情況，但是設(shè)計放電規(guī)則是一個難點，需要提出創(chuàng)新的思想和方法才行.

作者在研究全著色的過程中，考慮過通過設(shè)計全著色的色多項式來研究TCC.我們的出發(fā)點是希望能得到和點著色的色多項式一樣的公式，然后利用代數(shù)的知識來研究全著色.目前的研究還沒有成型，因此也希望感興趣的讀者在這方面貢獻(xiàn)力量.