圖的全著色研究綜述

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

1 引 言

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

在沒有特殊聲明的情況下，本文所言之圖都指簡單無向圖.對于給定圖G，分別用V(G)和E(G)表示G的頂點集和邊集.圖G中所含的頂點數和邊數分別稱為G的階和規模.若G的規模為0，即E(G)=?，則稱G為空圖.兩個頂點u,v∈V(G) (或兩條邊e1,e2∈E(G))稱為相鄰的如果uv∈E(G) (或e1,e2具有相同的端點).G中的頂點u和邊e稱為是關聯的如果u是e的一個端點.用NG(u)表示G中與頂點u相鄰的所有頂點的集合，并把|NG(u)|稱為u的度數，記為dG(u).分別用δ(G)和Δ(G)表示G的最小度和最大度.所有頂點度數都為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-部圖的每個部分所含的頂點數都相同，則稱其為等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中相鄰當且僅當它們在圖H中相鄰，則稱H為G的導出子圖，或由V(H)導出的子圖，記為G[V(H)].令U是圖G的一個頂點子集，如果U中任意兩個頂點在G中都相鄰，那么稱U為G的一個團；如果U中任意兩個頂點在G中都不相鄰，那么稱U為G的一個獨立集.

一個圖稱為路如果該圖的所有點和邊可以排列成一個點邊序列v1e1v2e2…vn-1en-1vn使得ei=vivi+1,i=1,2,…,n-1，并且序列中不含相同的點和相同的邊；如果在路v1e1v2e2…vn-1en-1vn的基礎上添加一條邊v1vn，所得之圖稱為圈.路和圈中所含的邊數稱為它們的長度.本文用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關聯，則f(u)≠f(e).

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

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

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

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

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

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

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

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

2.1 特殊圖類

下面介紹幾類滿足TCC的圖類，這些圖類不是很常見，但它們的結構都具有一定的規律可循.

定義2.1(Unitary Cayley圖)Unitary Cayley圖是定義在環R上的圖GR，它的頂點集V(GR)=R，即R中的每個元素對應GR中的一個頂點，邊集E(GR)={i,j∈R,i-j與R中所含的元素數互質}[15].文獻[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中每個頂點的度數屬于0,1,i-1,i-2中的一個，那么稱G是Mork Threshold圖.文獻[14](定理3.2)證明了此類圖滿足TCC.

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

為了構建具有大的色數但是具有小的團數的圖，1955年，Mycieski[16]引入了Mycielskian. 2003年，Lam等[17]將Mycielski圖進行了擴展，構造了廣義Mycielski圖并研究了此類圖的循環色數.關于廣義Mycielski圖的研究有很多，作者在2017年研究了此類圖的鄰點可區別全色數[18].

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

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

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

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

2.2 低度圖和高度圖

2.2.1 低度圖

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

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

證明定理2.5是全著色領域開創性的工作，其證明思路如下：

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

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

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

證明關于定理2.6的證明，只需考慮G是4-正則時的情況，這是因為任何一個最大度為Δ的圖都可以被嵌入到一個Δ-正則圖中.由于任意2n-正則多重圖，n≥1,都是2-可因子分解的[21](見文獻[12]引理4.7)，所以4-正則圖G可以分解成2個邊不交的2-因子F1，F2的并. 首先給圖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,…重新用另外兩種色進行正常2-著色之后，C1,C2,…中的邊就可以正常著色了，故定理得證.

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

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

2.2.2 高度圖

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

1987年，王建方等[23]通過設計一些變換，可以通過擴展一個(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]對其進行了改進，他們首先在一個圖的基礎上添加一個新的頂點，然后通過擴展新圖的邊著色來得到原圖的一個全著色.基于此方法，他們證明了TCC對于最大度大于等于|V(G)|-4的圖G成立.1992年，Yap等[25]又進一步將上述結論改進到|V(G)|-5.

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

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

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

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

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

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

2.3 全色數的若干上界

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

定理2.12[31]令常數c滿足11/6

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

定理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]通過研究邊色數(用′(G)表示圖G的邊色數)和點色數(用(G)表示圖G的點色數)與全色數之間的關系，得到了下面的上界.

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

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

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

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

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

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

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

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

文獻[38]中，McDiarmid等證明了另一個關于最大度的界.

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

1995年，Sánchez-Arroyo[39]改進了定理2.18的結論，他證明了如下定理.

定理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)

進一步，他證明了當n是任意奇數時，這些界都可達.

1987年，王建方等[41]進一步研究了圖與補圖的全色數，改進了Cook的結論.

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

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

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

3 第一類圖和第二類圖

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

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

3.1 完全圖和完全多部圖

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

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

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

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

定理3.1說明當n是奇數時完全圖Kn是第一類圖，否則是第二類圖.

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

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

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

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

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

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

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

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

關于判斷偶階完全多部圖是第一類圖的條件，直到2000年才有了一些進展.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]利用圖合并技術[52]，研究了具有較低def(G)的完全多部圖G的全色數，其中def(G)被稱為圖G的deficiency，定義為

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

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

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

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

3.2 密集圖

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

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

按定理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-階圖的全色數，他們證明了如下定理.

定理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中所有最大度頂點的導出子圖.2003年，Xie等[27]利用文獻[58]中的證明技巧，通過研究GΔ的結構，證明了下述結論.

定理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. 關于積圖全色數的研究主要集中在笛卡爾積，對后三種積圖的研究不是很多.這里統一給出這四種積圖的定義.

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

E(G□H)={(g,h)(g′,h′)|g=g′,hh′∈E(H) 或者h=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不一定同構.文獻[59]中，作者證明了笛卡爾積圖全色數與原圖全色數的關系.

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

關于積圖的全色數研究很多，主要集中于兩個結構簡單圖的積圖，比如路于路，圈與圈，完全圖和完全圖等等.下面對這些結論一一介紹.

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

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

定理3.12說明了Cm□Cn是第一類圖，該結論改進了前面Cm□Cn是第一類圖的結論.

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

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

此外，還有學者研究了corona積和deleted字典積的全著色.兩個圖的G和H的corona積圖[67]，記作GH(這里為了與字典積區分，用符號‘’代替原文中的符號‘°’)，是指由一個G的拷貝和|V(G)|個H的拷貝通過將G的第i個頂點與H的第i個拷貝中的每個頂點相連邊構成，其中1≤i≤|V(G)|.兩個圖G和H的deleted字典積圖[68]，記作Dlex(G,H)，是指具有頂點集V(G)×V(H)，邊集{(g,h)(g′,h′)|gg′∈E(G)且h≠h′, 或者hh′∈E(H)且g=g′}的圖.在文獻[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的邊色數是其最大度，那么對于任意至少含有3個頂點的圖H，Dlex(G,H)滿足TCC；特別地，如果G和H的邊色數都等于它們的最大度，那么Dlex(G,H)是第一類圖.最近，Vignesh等[69]又證明了如果G和H滿足TCC，那么它們的點corona積圖，邊corona積圖和鄰域corona積圖都是第一類圖.

3.4 弦圖

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

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

3.5 立方圖

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

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

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

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

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

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

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

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

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

關于問題4，目前沒有驗證的僅是階數為36和38的snarks.

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

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

3.6 其它圖類

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

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

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

在文獻[60]中，Seoud研究了這兩類圖的全色數，得到下面的結論.

定理3.13[60]任意兩個階數不同的路的聯圖是第一類圖；任意theta圖是第一類圖.

注意，定理3.13中構成聯圖的兩個圖要求階數不同，如果相同結果并非如此.比如P2+P2=K4，而K4是偶階完全圖，是第二類圖.

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

在文獻[78]中，Chetwynd證明了如下定理.

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

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

文獻[79]中，Mohan等證明了如下定理.

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

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

Vignesh等在文獻[68]中研究了完全圖Kn線圖的全色數，證明了：

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

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

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

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

在文獻[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]用兩篇文章研究了不含唯一弦和四邊形的圖的全色數.他們分別證明了：

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

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

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

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

定義3.12(循環圖)對于正整數序列1≤d1

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

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

定義3.13(Sierpiński圖)對于正整數n,k及k-階完全圖Kk，Sierpiński圖S(n,k)指具有頂點集{1,2,…,k}n，兩個頂點u=(u1,u2,…,un)和v=(v1,v2,…,vn)相鄰當且僅當存在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)的基礎上，收縮S(n,3)中每一條不在三角形上的邊，所得之圖稱為Sierpiński gasket圖[89]，記作S(n)(這里為了與星圖區別，所以用符號S(n)表示).Jakovac等[90]證明了對于任意n≥2,S(n)是第一類圖；對于任意n≥1和k≥1,T(S(n,k))≤k+2；特別地，對于任意n≥1，若k≥3是奇數，則S(n,4)和S(n,k)是第一類圖.對于k≥6是偶數的情況，它們猜想S(n,k)是第二類圖.然而，三年之后，Hinz等[91]通過研究Hanoi圖的著色，構造出了該猜想的反例，從而說明對于k≥6是偶數的情況，S(n,k)不一定全是第二類圖.Geetha等[92]研究了廣義的Sierpiński圖S(n,G)的全色數，他們證明了對于一些特定第一類圖G，比如房子圖，輪圖，圈的笛卡爾積圖等，S(n,G)是第一類圖.

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

4 平面圖的全色數

本節重點介紹平面圖全著色的研究進展，首先給出平面圖的定義.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

由于K4是最大度為3的平面圖且T(K4)=5，所以問題4.2中k應該屬于{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等在文獻[114]中證明了平面圖G如果不含弦l-圈，l=5,6，那么G有一個k-全著色，其中k=max{7,Δ(G)+1}, 這里弦l-圈指至少有一條弦的圈；注意到當Δ(G)≥6時，k=Δ(G)+1，所以此結論改進了Hou等[113]的結果.

最大度大于等于7的平面圖是第一類圖的充分條件包括：不含5-圈[115]；對于任意頂點v都存在一個整數kv∈{3, 4, 5, 6}使得v不與任意kv-圈關聯[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), 都存在一個整數kv∈{3, 4, 5, 6, 7, 8}使得v不與任意kv-圈關聯[124]；對任意頂點v∈V(G), 都存在兩個整數kv,lv∈{3, 4, 5, 6, 7, 8}使得v不與相交的kv-圈和lv-圈關聯[125]；對任意頂點v∈V(G), 都存在兩個整數kv,lv∈{3, 4, 5, 6, 7,}使得v不與相鄰的kv-圈和lv-圈關聯[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)不關聯弦6-圈或者弦7-圈或者2-弦5-圈[133]；每個頂點v∈V(G)關聯至多dG(v)-2?dG(v)/5」個三角形[134].

在文獻[135]中，Wang等研究了具有較小最大度的平面圖的全著色.令G是最大度為Δ圍長為g的平面圖，且存在整數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)}且每個頂點至多關聯一個長度為g的圈，那么G是第一類圖.

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

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

文獻[136]研究了外平面圖的鄰點可區別全著色，所得結論可以自然推廣到全著色上.

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

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

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

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

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

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

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

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

5 計算復雜性

6 結束語

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

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

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