平面圖的各種染色綜述

吳建良， 楊東雷， 楊 帆

(山東大學 數學學院， 山東 濟南 250100)

本文考慮的是簡單無向圖.有關概念和術語可以參考文獻[1-2]，染色方面的書籍有文獻[3-6]，一篇關于平面圖染色的英文綜述見文獻[7].圖一般由它的點集和邊集組成.首先第1節介紹平面圖的概念及其結構性質, 介紹幾個特殊的平面圖; 第2節介紹只染點方面的染色概念并綜述部分染色在平面圖方面的結果; 第3節介紹只染邊方面的染色,并綜述一些染色在平面圖方面的結果; 第4節介紹圖的全染色,列表全染色, 鄰點(和)可區別的全染色, 無圈全染色等概念并敘述平面圖相關的結果; 第5、6節首先介紹一些前面沒有提到的染色, 羅列一些主要結果,并提供一些可以繼續研究的問題.

1 平面圖及其結構性質

如果一個圖可以畫在一個平面上使得它的邊僅在作為公共端點的頂點處相交, 那么這樣的圖稱為可平面圖, 這種畫法稱作該圖的一個平面嵌入. 在后面說到平面圖時都默認為把平面圖已經嵌入到平面上了. 這樣平面圖的邊把平面分割成許多連通的區域, 我們把這些連通的區域稱為面, 用F(G)(簡記為F)表示圖G的面的集合.

設X是一個固定的圖. 在X中的一些邊上插入若干新的頂點，這樣所得到的圖叫做X的細分(Subdivision). 換句話說，就是把X中的一些邊換成長至少為2的路. 如果一個圖G不包含X的任何一個細分作為子圖,則稱G是X-SF-圖(X-subdivision-free graph). 用SF(X)來記所有X-SF-圖的集合.

如果圖X可以由圖G的一個子圖經過一系列的收縮邊而得到，就稱X是G的一個子式(minor). 如果一個圖G不包含X作為子式,則稱G是X-MF-圖(X-minor-free graph). 用MF(X)來記所有X-MF-圖的集合. 顯然有MF(X)?SF(X).

1930年Kuratowski(1)參見文獻[2]中的定理4.4.6.就得到定理：一個圖是平面圖當且僅當它是不含K5和K3,3的細分作為子圖的圖,即平面圖G∈SF(K5)∩SF(K3,3). 1937年Wagner得到了一個等價的定理：平面圖G∈MF(K5)∩MF(K3,3).

以上兩個結果雖然非常漂亮地刻畫了平面圖，但是很難得到平面圖的結構性質.而平面圖歐拉公式卻給人們帶來不少驚喜.著名的平面圖歐拉公式表述如下：設G是一個連通平面圖, 則

|V|-|E|+|F|=2.

對f∈F(G),用與面f相關聯的邊的條數(其中割邊計算兩次)稱為面的度, 記為dG(f), 簡記為d(f). 易知:∑v∈V(G)d(v)=∑f∈F(G)d(f)=2|E(G)|. 把歐拉公式寫成如下形式：

∑v∈V(G)(d(v)-4)+∑f∈F(G)(d(f)-4)=-8

或

∑v∈V(G)(d(v)-6)+∑f∈F(G)(2d(f)-6)=-12

等.把左邊括號內的值分別定義為點或面的初值ch.由于右邊是個負數，點和邊中肯定有元素的初值是負的.這個變形在研究平面圖的染色問題時非常有用，因為如果某個染色結果不成立，可以通過從初值為正的元素傳一些值給初值為負的元素，使得它們的值全部非負，這樣就使得歐拉公式不成立，從而導出矛盾.

另外，平面圖還有一些子類：系列平行圖、外平面圖、k-外平面圖、k-邊界平面圖、Halin圖等.這些圖類有更好的結構性質，在染色方面的結果都做得比較徹底.

?系列平行圖：不包含K4作為子式的圖，也叫K4-MF-圖.

?外平面圖：不包含K4和K2,3作為子式的圖. 外平面圖的頂點都與無窮外面關聯.

?k-外平面圖：把外平面圖記作1-外平面圖.當k≥2時，把k-外平面圖的無窮邊界上的點都刪除以后就得到(k-1)-外平面圖.

?k-邊界平面圖：頂點落在至多k個面的邊界上的平面圖叫k-邊界平面圖.顯然，外平面圖就是1-邊界平面圖.

?Halin圖：設G(V,E,F)是一個3-連通平面圖.如果G去掉與無窮外部面關聯的邊后得到的是一棵樹，則稱G為Halin圖.

2 平面圖的點染色

2.1 染色定義

圖的染色理論開始于四色問題. 圖的正常點染色(Vertex coloring)是指用顏色1,2,…,k對圖的每個頂點分配一個顏色，使得相鄰的頂點染色不同，染色所用的最少顏色數k就稱為圖的點色數. 四色問題就是問平面圖是不是4-可染的. 如果在正常染色的基礎上加上某個條件，就可以得到如下染色：

?均勻染色(Equitable coloring): 對圖的一個正常點染色，如果任何兩個不同的顏色所染的頂點數至多差1，那么就稱此染色是均勻的；最小的顏色數稱為圖G的均勻色數，記為=(G). 如果對最小的k使得對所有的整數t≥k，圖G都存在一個均勻染色，這個k就稱為G的均勻色閾值，記為≡(G).

?無圈點染色(Acyclic coloring): 對圖的一個正常點染色，如果任何兩個不同的顏色所染的點集合所導出的子圖是一個森林, 那么就稱此染色是無圈的；最小的顏色數稱為圖G的無圈點色數，記為a(G).

?線性染色(Linear coloring): 任何兩個不同的顏色所染的點集合所導出的子圖是一個線性森林.

?(p,q)-標號((p,q)-labelling)：相鄰的頂點的顏色至少差p，距離為2的兩個點的顏色至少差q. (1,0)-標號就是我們說的正常點染色.(1,1)-標號又叫2-距離染色.

?鄰點可區別的點染色(Adjacent vertex distinguishing vertex coloring):任何相鄰的兩個點所對應的鄰域的染色集合不同.

?鄰和可區別的點染色(Adjacent sum distinguishing vertex coloring): 任何相鄰的兩個點所對應的鄰域的顏色之和不相等.

?r-色調染色(r-hued coloring):度數為d的頂點鄰域至少出現min{d,r}種顏色.

?鄰域r-限制染色(Neighborhoodr-bounded coloring)：每個點的同色鄰點數不得超過r個. 如果不要求正常染色，筆者有如下染色：

?(k,d)*-染色: 用k種顏色去染圖的點使得染同色點集合的導出子圖的最大度至多為d;

?點蔭度和線性點蔭度：用k種顏色去染圖的點使得染同色點集合的導出子圖是一個最大度至多為t的森林，所用最少的顏色數稱為圖的t-點蔭度. 如果森林的最大度沒有限制，即t為無窮大，就稱為圖的點蔭度(Vertex arboricity),記為va(G)； 如果t=2, 就稱為圖的線性點蔭度(Linear vertex arboricity),記為vla(G). 當然還有：

?圓染色(Circular coloring): 給一個周長為k的圓環L(k≥2),圖G的每個點對應于L上長度為1的半開弧. 如果兩個點相鄰，它們對應的弧不交，就說G是k-圓可染的. 最小的k稱為G的圓色數. 這個概念有幾個等價的定義, 如: 假設1≤2d≤k, 如果用k種顏色給圖的每個點一個顏色且存在某個染色φ使得任何相鄰的兩個點u,v都有d≤|φ(u)-φ(v)|≤k-d，則稱G存在k/d-圓染色. 最小的k/d稱為G的圓色數.

?分數染色(Fractional coloring): 用k種顏色給圖的每個點染d種顏色. 如果任何相鄰的兩個點所染顏色的集合不交，則稱G存在k/d-染色. 最小的k/d稱為G的分數色數.

?(k,d)-可選的((k,d)-choosable): 如果給圖G的所有點v都分配一個顏色集合L(v)(也叫色列表)且G存在一個正常的點染色φ使得對每個點v∈V(G)都有φ(v)∈L(v),則稱圖G是L-可染的. 如果對滿足下列兩條的任何色列表L：

(1)對任意的v∈V(G), 都有|L(v)|≥k，且

(2)對任意相鄰的兩個點u和v, 有|L(u)∩L(v)|≤d;

G是L-可染的，則稱G是(k,d)-可選的, 也稱G有一個(k,d)-列表染色. 最小的k稱為G的d-可分離的列表色數如果k=d, 就把G是(k,d)-可選的簡稱為G是k-可選的, 也說G有一個k-列表染色. 最小的k稱為G的列表色數list(G)，等等.

除了以上染色外，還考慮了把上述兩個概念相結合得到新的染色概念，如：均勻列表染色、無圈列表染色、鄰點(和)可區別的列表染色、圓點蔭度、列表分數染色等.這些概念就不詳細地給出定義了.

本節的其余部分將敘述平面圖的點染色和列表點染色、點蔭度和線性點蔭度、均勻染色和均勻點蔭度、無圈點染色、(k,d)-列表染色等方面的結果.

2.2 平面圖的點染色與(k,d)-可選性

由四色定理可知，平面圖是4-可染的，而4也是最好的界.接下來一個自然的問題就是：什么樣的平面圖是3-可染的？已知判斷一個平面圖是否3-可染是NP-完全的，因此尋找3-可染的充分條件也是該方向的一個重要研究課題.一個經典的結果是Gr?tzsch[8]在1959 證明了任意一個不含三角形的平面圖是3-可染的.此外，如果平面圖G不含5-圈且兩個3-圈的距離至少為2[9]; 或者G不含5-圈, 7-圈和兩個3-圈不鄰[10]，那么G是3-可染的.

相較于點染色，平面圖的列表染色要復雜得多.Voigt[11]構造了一些不是4-可選的平面圖，Thomassen[12]在1994年非常漂亮而又非常簡單地證明了每個平面圖是5-可選的.目前這個結果已經推廣到了K5-minor free圖[13]以及局部平面圖[14].

這樣自然會有一個問題：哪些平面圖是4-可選的，哪些是3-可選的？有關3-可選的第一個結果是由 Alon等[15]在1992得到的，他們證明了平面二分圖是3-可選的.隨后Thomassen[16]證明了圍長為5的平面圖是3-可選的.該定理的證明方法借鑒了5-可選的證明思路，而這個圍長條件也是緊的[17].2009年Li[18]巧妙地證明了4-圈不與4-圈和5-圈相交的平面圖是3-可選的，該結論推廣了Thomassen的結果.以下列出平面圖是3-可選的一系列充分條件：

?圖G不含長度為4和9的圈，同時不含長度為{5，6，7，8}中任兩數的圈[19].

?圖G不含長度為3, 5, 6的圈[20].

?圖G不含長度為4, 5的圈且任兩個三角形距離至少為4；或者圖G不含長度為4, 5, 6的圈且任兩個三角形距離至少為3[21].

?圖G不含長度至多為10且含一弦的圈[22].

?圖G不含長度為3,7,8 的圈[23].

?圖G中兩個長度至多為4的圈的距離至少為26[24].

?圖G不含長度在4至8之間的圈[25].

關于4-可選也有很系統的研究結果.運用歐拉公式很容易得出任何不含3-圈的平面圖是3-退化的，因此也是4-可選的.Wang等[26]把此結果推廣到了不含相交三角形的平面圖. 關于平面圖是4-可選的還有如下一些充分條件：①不含i-圈(i∈{4,5,6,7})；②不含相鄰于三角形的4-圈；③每個5-圈不同時相鄰3-圈和4-圈; ④不含相交5-圈; ⑤不含弦6-圈.

1998年Kratochvíl等[27]把列表染色概念擴充到了(k,d)-可選性(Choosability with separation), 并證明了平面圖是(4,1)-可選的, 同時猜想平面圖是(4,2)-可選的. 這個猜想對沒有弦k-圈(k=5,6或7)的平面圖是成立的.krekovski[28]指出存在無3-圈的平面圖不是(3,2)-可選的，同時他猜想平面圖是不是(3,1)-可選的? 目前平面圖是(3,1)-可選的條件有：

?沒有3-圈.

?沒有4-圈.

?沒有5-圈和6-圈.

?對5≤i≤6,5≤j≤7, 任何i-圈和j-圈都不鄰.

2.3 均勻點染色和均勻點蔭度

Hajnal和Szemerédi(2)Hajnl A, Szemerédi E. Proof of a conjecture of P.Erd?s, in: P.Erd?s A, Rényi VT, Sós (Eds.). Combinatorial Theory and its Applications, North-Holand, London, 1970： 601-623.在1970年證明了如下著名的定理: 對于任意的正整數r，任意一個最大度至多為r的圖都存在一個均勻(r+1)-染色.對這一經典結論，2008年Kierstead等[29]給出了一個簡化的證明，同時也給出了一個找此均勻染色的多項式時間算法.另一方面，早在1973年Meyer猜想(ECC)(3)Meyer W. Equitable coloring. American Mathematical Monthly, 1973，80: 920-922.: 如果圖G不是Km,C2m+1, 那么存在一個r(≤Δ(G))使得G是均勻r-染色的.而Chen等[30]在1994年提出了一個加強版的猜想(EΔCC)：如果圖G不是Km,C2m+1,K2m+1,2m+1, 那么G存在一個均勻Δ(G)-染色， 即≡(G)≤Δ(G).并且證明了當最大度Δ(G)≥3或者Δ(G)≥|G|/2時，該猜想是成立的.直到2012年Chen等[31]將結果改進到了Δ(G)≥|G|/3+1.

關于平面圖的均勻染色，Yap和Zhang證明了對于最大度至少為13的平面圖，EΔCC-猜想時成立的.到目前為止改進到最好的界是最大度至少為9的平面圖[32].下面列出近些年已知的滿足EΔCC-猜想的一些特殊平面圖：①系列平行圖；②Δ≥5且圍長大于等于6的平面圖; ③Δ≥6且不含三角形，或者不含4-圈和6-圈的平面圖; ④Δ≥7且不含4-圈的平面圖. 這幾個結果有些在列表的情況下也是成立的，關于平面圖的均勻列表染色還有不少結果.Wu等[33]證明了: Δ≥3且對圍長至少為26的非二部平面圖，或者圍長至少為4的2-連通的外平面圖，有≡(G)=(G).由此可以提出一個問題：什么情況下，均勻色數閾值等于點色數？2011年Fan等[34]證明了ECC猜想的一個松弛情況：任何簡單圖都存在一個均勻的非正常Δ-染色，使得每個顏色所染點的導出子圖是一些孤立邊. 隨后，Wu等[35]提出了均勻點蔭度的概念，并給出了猜想：①所有圖的均勻點蔭度至多為「(Δ+1)/2?; ②所有平面圖的均勻點蔭度不超過一個常數. 最近，Esperet等(4)Esperet L, Lemoine L, Maffray F. Equitable partition of graphs into induced forests. Discrete Math, 2015, 338(8):1481-1483.證明了：任何至少有兩個點的連通圖的均勻點蔭度小于無圈點色數. 因為平面圖的無圈點色數不超過5，所以由此推出：平面圖的均勻點蔭度不超過4，驗證了猜想的第②部分.根據此結果，筆者猜想：平面圖的均勻點蔭度不超過3.

2.4 無圈點染色

無圈點染色是在正常點染色的基礎上加強了限制：要求每個圈上都至少出現3種顏色.這個概念最早是由Grünbaum[36]提出的，同時他在文中證明了任意一個平面圖是無圈9-可染的.經過了學者們的不斷改進，最終Borodin[37]證明了任意一個平面圖是無圈5-可染的，并且證明了5是緊的上界. 這個結果被Mohar[38]推廣到了局部平面圖上了.Kostochka等[39]也構造一個2-退化的二部平面圖，不是無圈4-可選的.而Borodin等[40]證明了對于不含三角形的平面圖，該結果可以改進到4，對于圍長至少為7的平面圖，可以改進到3.從計算復雜度的角度來看，Kostochka[41]證明了判斷一個圖是否是無圈k-可染的(任給k≥3)，還是NP-完全的.

考慮列表形式的無圈染色，Borodin等[42]證明了任意一個平面圖都是無圈7-可選的，并且猜想：任意一個平面圖都是無圈5-可選的.此猜想對兩類特殊的平面圖是成立的：①不含4-圈的平面圖;②任意一個3-圈不鄰{3，4，5}-圈并且4-圈不鄰{4，5，6}-圈.一個平面圖是無圈4-可選的，如果它滿足以下任意一個條件：①圍長為5;②不含{4，5，6}-圈；③不含{4，5，7}-圈；④不含{4，5}-圈以及相交三角形;⑤沒有4-圈和三角化6-圈;⑥沒有{4，5}-圈以及三角弦8-圈;⑦沒有{4，7，8}-圈;⑧沒有{4，5}-圈的平面圖.Montassier等[43]猜想：不含4-圈的平面圖是無圈4-可選的.而后Borodin等[44]證明了任意的3-圈不鄰{3,4,5,6}-圈且4-圈不鄰{4，5，6，7}-圈的平面圖是無圈4-可選的.同時他們提出了問題：是否任意一個4-圈不鄰(≤4)-圈的平面圖都是無圈4-可選的？Borodin等[45]證明了圍長為7的平面圖是無圈3-可選的，而且他們也猜想:圍長為5的平面圖都是無圈3-可選的.

以下三個結果是非平面圖的.

?任意一個環面圖是無圈8-可選的[46].

?任意一個1-平面圖是無圈20-可染的[47].

?所有的局部平面圖是無圈7-可染的[48].

2.5 點蔭度和線性點蔭度

給定一個圖G，令va(G)表示最小的整數k使得圖G存在一個k-染色，其中每個色類的導出子圖都是一個森林.作為圖的正常點染色的弱化，這個概念是由Chartrand等[49]首先定義的.并且他們證明了va(G)≤max{(1+δ(H))/2:H?G}.由此可以推出：任何平面圖G, 有va(G)≤3. Hakimi等[50]指出判定極大平面圖的點蔭度為2的問題都是NP-完全的, 同時他們證明了一個平面圖的點蔭度為2當且僅當它的對偶圖(Dual graph)有一個連通歐拉支撐子圖.平面圖G的點蔭度至多為2的充分條件有:①不含i-圈，其中i可取4、5、6中的任意一個;②任意兩個3-圈距離至少為3；③兩個3-圈不共點;④G不含弦6-圈;⑤5-圈不交;⑥5-圈不同時相鄰于3-圈和4-圈.這些結果有些證明是列表情況.

圖G的線性點蔭度vla(G)的概念是由Harary[51]提出的，其要求每個色類的導出子圖是一個線性森林(一些不交的路).Poh[52]證明平面圖G的線性點蔭度vla(G)≤3.

3 平面圖的邊染色

3.1 邊染色方面的定義

圖G的線圖L(G)是指把G的邊集作為L(G)的點集,L(G)中的兩個點相鄰當且僅當它們在G中的邊相鄰. 圖G的正常邊染色(Proper edge coloring)、無圈邊染色(Acyclic edge coloring)、強邊染色(Strong edge coloring)、(p,q)-邊標號((p,q)-edge labelling)、 圓邊染色(Circular edge coloring)、 分數邊染色(Fractional edge coloring)、(k,d)-邊可選的((k,d)-choosable)、列表邊染色(List edge coloring)、無圈列表邊染色(Acyclic list edge coloring)分別就是L(G)的正常點染色、無圈點染色、2-距離標號、(p,q)-標號、 圓染色、 分數染色、(k,d)-可選的、列表邊染色和無圈列表邊染色.所用最小的顏色數稱為圖G的邊色數、無圈邊色數、強邊色數、(p,q)-邊標號數、圓邊色數、分數邊色數、(k,d)-邊可選數、列表邊色數和無圈列表邊色數，分別用′(G)、、和ac′list(G)表示.除以上邊染色外，人們還研究了如下邊方面的染色：

?鄰點(和)可區別的邊染色(Adjacent vertex(sum) distinguishing edge coloring): 對圖G的一個正常邊染色φ，令Cφ(v)={φ(uv):uv∈E(G)}和cφ(v)=∑uv∈E(G)φ(uv).如果任何相鄰的兩個點u和v，有Cφ(u)≠Cφ(v)，那么稱此邊染色為圖的鄰點可區別的邊染色，最小的k稱為圖的鄰點可區別的邊色數，記為′adj(G)或′adj；如果任何相鄰的兩個點u和v，有cφ(u)≠cφ(v)，那么就稱此邊染色為圖的鄰和可區別的邊染色，最小的k稱為圖的鄰和可區別的邊色數，記為或關于鄰點(和)可區別的列表邊色數，記為或

?均勻邊染色(Equitable edge coloring): 對圖G的一個邊染色(不需要正常)，如果對所有的頂點，與它關聯的邊中任何兩個不同的顏色所染的邊數至多差1，那么就稱此邊染色是均勻的.

?(k,d)-蔭度：用t種顏色去染圖的邊使得染同色的邊導出子圖是一個森林并且森林的每個連通分支的最大度至多為k和直徑至多為d，所用最少的顏色數稱為圖的(k,d)-蔭度. 如果k和d都為無窮大，(k,d)-蔭度又稱為圖的蔭度(Arboricity), 記為a(G)； 如果k=2且d為無窮大, (k,d)-蔭度又稱為圖的線性蔭度(Linear arboricity),記為la(G); 如果k=t=2, (k,d)-蔭度又稱為圖的線性2-蔭度(Linear 2-arboricity),記為la2(G).

以上這幾個染色也均有列表情況.下面主要敘述以上幾個染色在平面圖方面獲得的一些結果.

3.2 正常邊色數

關于正常邊染色，有著名的Vizing定理(參見文獻[4-6])：對任何簡單圖G，有Δ≤′(G)≤Δ+1. 如果′(G)=Δ，則稱G是第一類圖，否則稱G是第二類圖.在平面圖方面，還是Vizing首先證明：最大度至少是8的平面圖是第一類圖， 同時他還提出如下猜想(平面圖的邊染色猜想, ECC)：最大度至少是6的平面圖是第一類圖.Zhang[53]以及Sanders等[54]分別證明了此猜想在Δ=7的情況是成立的.所以此猜想只有Δ=6還沒有被完全解決.關于平面圖G是第一類的還有如下條件:

?Δ=6且滿足以下條件之一：①每個點至多關聯三個三角形；②不含弦k-圈，其中k∈{3,4,5,6,7}; ③任意5-圈至多包含1條弦；④任意6-圈至多包含2條弦;⑤任意兩個7-圈不鄰；⑥任意k-圈至多鄰1個k-圈，其中k∈{3,4,5}.

?Δ=5且滿足以下條件之一：①不含4-圈或5-圈；②任意3-圈與4-圈不鄰；③每個點至多關聯一個三角形.

?(Δ，g)∈{(5,4),(4,5),(3,8)},其中g是圍長.

3.3 列表邊色數

列表邊染色的概念首先由Vizing[55]提出，而后Borodin等[56]提出了一個非常具有挑戰性的猜想——列表邊色數猜想：對所有的圖G，有′(G). 顯然′(G)≤對平面圖，如果滿足如下條件之一，此猜想就成立.

?Δ≥12[32].

?Δ≥10且①任何7-圈至多含兩條弦，或②任何6-圈至多含一條弦.

?Δ≥8且滿足以下條件之一：①不含弦5-圈；②4-圈不鄰；③3-圈與4-圈不鄰；④3-圈與5-圈不鄰.

?Δ≥8且滿足以下條件之一：①不含弦5-圈；②4-圈不鄰；③3-圈與4-圈不鄰；④3-圈與5-圈不鄰.

?Δ≥7且滿足以下條件之一：①4-圈與4--圈不鄰；②同時不含5-圈和6-圈.

?Δ≥6且同時不含4-圈和6-圈.

?Δ≥5且g≥5或Δ≥4且g≥6或Δ≥3且g≥10.

?(Δ,k)∈{(7,4),(6,5),(5,8),(4,14)},不含長度從4到k的圈，其中k≥4.

同時對平面圖G，滿足充分條件如下：

?Δ≥8[57].

?Δ≥7且①任何7-圈至多含兩條弦，或②任何6-圈至多含一條弦.

?Δ≥6且G滿足以下條件之一：①3-圈不鄰或不含7-圈；②3-圈與5-圈不鄰；③不含弦5-圈；④不含弦6-圈；⑤4-圈不鄰.

?Δ≥5且G滿足以下條件之一：①同時不含弦5-圈和弦4-圈；②同時不含弦5-圈和弦6-圈；③3-圈和4-圈不鄰；④不含5-圈.

?Δ≤4[58].

3.4 無圈邊色數

同樣，也可以將無圈邊染色推廣到無圈列表邊染色，這方面的結果相對較少并且都是限制在特殊圖類上，如外平面圖[63]、Halin圖的剖分[64]等.

3.5 強邊色數

因為強邊色數一般比較大,想獲得強邊色數的確切值是非常困難的.Erd?s等[65]提出猜想:對任意圖G，當Δ取偶數時，否則此猜想在Δ≤3的情況下是成立的.對最大度至少是3平面圖, 一般的界是:下面主要介紹平面圖的一些其他結果：

3.6 均勻邊色數

如果和點染色一樣，要求在正常邊染色的基礎上使得任何兩個顏色染的邊數之差不超過1，這個問題就變得非常容易了，因為Werra[67]已經證明了：如果一個圖存在正常k-邊染色，就一定存在這樣的均勻k-邊染色.所以均勻邊染色的概念就變成了前面所給的定義，它要求在所有點的關聯邊里每個顏色均勻的出現.關于這方面的第一個主要結果是由Hilton等[68]獲得的：設G是簡單圖且k≥2，如果G中的所有點的度均不能整除k,則G是均勻k-邊可染的.2011年Zhang等[69]推廣并證明了Hilton提出的一個猜想：設G是簡單圖且k≥2,如果G中的所有度數能整除k的點集合導出的是一個森林,則G是均勻k-邊可染的.2017年Hu等[70]創造性地證明了：對任何至少為12的整數k，所有的平面圖都存在一個均勻k-邊染色.由于證明過程用到的都是以前的基本工具，所以他們提出猜想：對所有整數k(≥6)，任何平面圖都存在一個均勻k-邊染色.如果這個猜想成立，那么平面圖的邊染色猜想也是成立的.

2001年Wu[71]提出概念：如果對所有的整數k(≥1), 一個圖G都存在一個均勻k-邊染色，那么G就稱為是均勻的.同時他證明：連通的外平面圖是均勻的當且僅當它不是含有奇數個點的歐拉圖.這一結果在2007年被Song等[72]推廣成系列平行圖.

3.7 鄰點(和)可區別邊色數

如果一個圖包含只有一條邊的連通分支，那么這個圖是沒有鄰點或鄰和可區別的邊染色.因此本節都假設圖不包含只有一條邊的連通分支，這樣的圖稱為正規圖.鄰點可區別的邊染色問題是由Zhang等在文獻[73]中提出來的，他們猜想(AVECC)：如果G是含至少6個點的連通圖，則≤Δ(G)+2.同時他們驗證了此猜想對樹、圈、路、完全圖以及完全二部圖是成立的.2014年Horňk等[74]證明：如果G是正規連通平面圖，則因為對任何圖G, 有∑(G),所以下面的猜想(A∑ECC)推廣了AVECC：如果G是正規連通圖且G≠C5,則Δ≤在平面圖方面，Wang等[76]證明了：如果G是正規連通平面圖，則同時Bonamy等[77]證明了：對Δ≥28的正規連通平面圖G，有′∑(G)=Δ(G)+1.此外，對一些特殊的平面圖，也有一些相關的結果.

3.8 平面圖的蔭度、線性蔭度、線性k-蔭度以及列表情況

圖G的線性蔭度la(G)就是把G的邊分解成線性森林的最少個數.關于線性蔭度，有著名的猜想：所有圖G的線性蔭度滿足la(G)≤「(Δ(G)+1)/2?[78]. Wu等[79-80]證明此猜想對所有平面圖是成立的.吳建良[81]猜想(LAC, 此猜想也出現在文獻[82]中)： 對最大度至少為5的平面圖G, 有la(G)=「Δ(G)/2?. 此猜想對滿足如下條件之一的平面圖是成立的：

(1)Δ(G)≥9[82];

(2)Δ(G)≥7且①不含弦i-圈(i∈{4,5,6,7}),或②5-圈至多含一弦，或③7-圈至多含兩弦，或④對任一點v∈V(G), 都存在兩整數iv,jv∈{3,4,5,6,7,8}使得與v關聯的兩個長度分別為iv和jv的圈是不相鄰的；

(3)Δ(G)≥5, 且①不含4-圈，或②不含相交的4-圈和相交的5-圈,或③不含帶弦的5-圈和6-圈;

(4)Δ(G)≥3, 且圖G的圍長g≥6.

圖G的線性k-蔭度lak(G)是指G的邊分解成長度不超過k的線性森林的最少個數.圖的線性k-蔭度最早是由Habib等[85]提出的，他們也給出了相應的猜想. 目前關于平面圖的線性k-蔭度的最好的界是由Wang等[86]給出的：對任何平面圖G, 有la2(G)≤「(Δ(G)+1)/2?+6.另外，王維凡等在外平面圖和不含4-圈的平面圖上也獲得了一些非常有價值的結果.

4 平面圖的全染色

4.1 平面圖的全染色和列表全染色

一個圖的全染色是指對圖G的點和邊都染色，使得相鄰和相關聯的元素之間都染不同的顏色. 圖G的全色數″(G)定義為圖G的所有全染色中所用最少顏色的數量. 著名的全染色猜想為(TCC)[87-88]：任意簡單圖G，Δ(G)+1≤″(G)≤Δ(G)+2. 有關一般圖全染色方面的結果可參見文獻[5]. 對平面圖, 此猜想只有最大度為6時沒有完全證明. 2008年前經過好幾篇文章的接力最終證明了：最大度至少為9的平面圖G有″(G)=Δ(G)+1. 從而在2009年Shen等[89]提出了平面圖的全染色猜想(Planar-TCC)：最大度為4到8之間的平面圖G有″(G)=Δ(G)+1. 此平面圖的全染色猜想是成立的，如果滿足下列條件之一：

?Δ(G)≥8且對G中任一頂點x,都存在整數k∈{3,4,5,6,7,8}使x至多關聯一個k-圈.

?Δ(G)≥8且對G中任一頂點x,都存在兩整數i,j∈{3,4,5,6}使任意兩個經過x的長度為i和j的圈都不相鄰.

?Δ(G)≥8且①沒有5-扇, 或②不含帶兩弦的5-圈, 或③不含相鄰弦5-圈, 或④不含相鄰弦7-圈, 或⑤不含帶兩弦的6-圈, 或⑥弦6-圈不相鄰, 或⑦不含帶3弦的7-圈.

?Δ(G)≥7且對G中任一頂點x, 都存在整數k∈{3,4,5,6,7,8}使x不關聯任一個k-圈.

?Δ(G)≥7且對G中任一頂點v, 都存在整數iv∈{3,4,5,6}使v不在任一個iv-圈上.

?Δ(G)≥7且不含①弦i-圈, 這里i=5,6或者7, 或② 3-圈相鄰于5--圈, 或③ 5-圈和6-圈, 或④相交3-圈, 或⑤相鄰的4-圈和相鄰的5-圈, 或⑥ 相交的6-圈.

?Δ(G)≥6且圖G不含①相交的4-圈，或②相交的3-圈、5-圈或者6-圈, 或③ 4-圈, 或④相鄰的4--圈.

?Δ(G)≥5且圖G沒有4-圈和6-圈.

?圖G的最大度和圍長(Δ,g)∈{(7,4),(5,5),(4,6),(3,10)}.

?(Δ,k)∈{(7,4),(6,5),(5,7),(4,14)}且圖G沒有長度在4至k之間的圈.

?(Δ,k)∈{(6,4),(5,5),(4,11)}，圖G不含相交3-圈且沒有長度在4至k之間的圈.

關于圖G的列表全色數有猜想：如果G是一個簡單圖，則″(G)[56]. 這確實是一個非常有挑戰性的猜想，目前對一般圖的結果非常之少. 關于平面圖，有兩類結果. 一類是關于的，它需要有如下條件之一：

?Δ(G)≥9[90].

?Δ(G)≥7且①沒有弦7-圈, 或②沒有5-扇, 或③每個3-圈至多與其他一個3-圈相鄰.

?Δ(G)≥6且不滿足：①弦6-圈, 或②3-圈與5-圈相鄰, 或③ 3-圈與4-圈相鄰.

?Δ(G)≥5且沒有：①弦5-圈和弦4-圈, 或②弦5-圈和弦6-圈, 或③ 3-圈或4- 圈, 或④ 5-圈.

?Δ(G)≥12[56].

?(Δ,k)∈{(7,4),(6,5),(5,8),(4,14)}且圖G沒有長度在4至k之間的圈.

?Δ(G)≥8且①不含弦5-圈, 或②不含相鄰4-圈, 或③ 3-圈與4-圈不相鄰, 或④ 3-圈和5-圈不鄰.

?Δ(G)≥7且任4-圈不相鄰于4--圈, 或者沒有5-圈和6-圈.

?Δ(G)≥6且沒有4-圈和6-圈.

4.2 鄰點(和)可區別的全染色

用k種顏色對G的點和邊進行一個全染色ψ, 用Cψ(v)來表示點v的顏色以及與v關聯邊的顏色集合. 如果對任何相鄰的兩個點v和u，都有Cψ(u)≠Cψ(v)，就稱這種全染色是鄰點可區別的，ψ稱為G的一個鄰點可區別的k-全染色, 并稱G是k-鄰點可區別全可染的.G具有k-鄰點可區別全染色的最小的k稱為圖G的鄰點可區別全色數, 記做在文獻[91]中, Zhang等提出了這個染色的概念, 并研究了樹、圈、輪、完全圖、完全二分圖等圖的這種染色, 然后提出了猜想(稱為鄰點可區別的全染色猜想，簡記為NVD-TCC): 對于至少有兩個點的圖G滿足

Δ(G)+1≤

設G有一個用顏色1,2,…,k染的全染色ψ, 筆者用cψ(v)來表示點v的顏色以及與v關聯邊的顏色的和值. 如果對任何相鄰的兩個點v和u，都有cψ(u)≠cψ(v)，就稱這種全染色是k-鄰和可區別的，ψ稱為G的一個k-鄰和可區別全染色, 并稱G是k-鄰和可區別全可染的.G具有k-鄰和可區別全染色的最小的k稱為圖G的鄰和可區別全色數, 記做類似地可以定義圖的鄰和可區別全-k-列表染色和鄰和可區別列表全色數記為鄰和可區別全染色的概念是由Pilsniak等[97]在2015年提出的. 他們研究了圈、路、星、完全圖、二分圖以及最大度不超過3的圖, 發現這些圖的鄰和可區別全色數都不超過Δ+3, 于是類似于鄰點可區別全染色, 他們提出了猜想(稱為鄰和可區別的全染色猜想, NSD-TCC): 對于至少有兩個點的圖G, 有

Δ(G)+1≤

4.3 無圈全染色

給定圖G的一個正常全染色ψ，如果任何一個圈上的點和邊至少染了4種顏色，則稱這種全染色為圖的無圈全染色，最小的顏色數稱為圖的無圈全色數，記為無圈全染色的概念首先由Sun等[105-106]提出，并得到了平面圖方面的一些相關結果.

5 與平面圖的面有關的染色

下面的三個染色因為要對平面圖的面進行染色，它們是平面圖的專屬染色：①平面圖的點面染色：對平面圖的點和面進行染色，使得相鄰的點、相鄰的面、相關聯的點和面之間都染不同的顏色.所用最少的顏色數稱為平面圖的點面色數，記為vf(G)； ②平面圖的邊面染色: 對平面圖的邊和面進行染色，使得相鄰的邊、相鄰的面、相關聯的邊和面之間都染不同的顏色.所用最少的顏色數稱為平面圖的邊面色數，記為ef(G)； ③平面圖的點邊面染色: 對平面圖的點、邊和面進行染色，使得任何兩個相鄰或相關聯的元素之間都染不同的顏色.所用最少的顏色數稱為平面圖的點邊面色數，也叫完備色數，記為vef(G). 人們已經證明了：對任何平面圖G，vf(G)≤6,ef(G)≤Δ(G)+3,vef(G)≤Δ(G)+4. 其他結果參見文獻[7].

6 可以繼續探討的一些問題

今后可以繼續研究的問題：

(1)改進現有結果，降低現有的上界，證明相關猜想或者得到一部分結果.例如，證明4-圈不交的平面圖是列表4-可染的；

(2)考慮多種染色的組合，研究新的染色，獲得比現有結果更一般的結果，例如，可以在考慮鄰和可區別的邊染色時要求相鄰兩點的色和至少差k(k>0)，或者在正常染色的基礎上再要求增加一條邊兩個端點所關聯的邊中至多有k個相同色，等等.

(3)把相關的結果擴展到更一般的圖類.人們知道利用平面圖的證明思想，以上染色在1-平面圖方面獲得了許多優秀的成果，關于嵌入到曲面上的圖和局部平面圖也有不少研究，但有些染色在這些圖類上的研究還是一片空白.另外，還可以考慮不含K5作為子式的圖和不含K3,3作為子式的圖.

后記： 限于篇幅，還有許多關于平面圖的染色方面的結果沒有列出，它們都是很有價值的，例如：圓染色(Circular coloring)、 多重染色(Multiple coloring)、分數染色(Fractional coloring)、適應點染色(Adaptive coloring)、對策染色(Game coloring)、DP-染色(DP-coloring),等等.另外，本文列出的一些結果也沒有標出出處，讀者可以從主要結果的被引處找到它們，在此謹向這些論文的作者們表示深深的歉意.