平面圖的各種染色綜述

吳建良， 楊東雷， 楊 帆

(山東大學(xué) 數(shù)學(xué)學(xué)院， 山東 濟(jì)南 250100)

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

1 平面圖及其結(jié)構(gòu)性質(zhì)

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

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

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

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

以上兩個(gè)結(jié)果雖然非常漂亮地刻畫(huà)了平面圖，但是很難得到平面圖的結(jié)構(gòu)性質(zhì).而平面圖歐拉公式卻給人們帶來(lái)不少驚喜.著名的平面圖歐拉公式表述如下：設(shè)G是一個(gè)連通平面圖, 則

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

對(duì)f∈F(G),用與面f相關(guān)聯(lián)的邊的條數(shù)(其中割邊計(jì)算兩次)稱為面的度, 記為dG(f), 簡(jiǎn)記為d(f). 易知:∑v∈V(G)d(v)=∑f∈F(G)d(f)=2|E(G)|. 把歐拉公式寫(xiě)成如下形式：

∑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

等.把左邊括號(hào)內(nèi)的值分別定義為點(diǎn)或面的初值ch.由于右邊是個(gè)負(fù)數(shù)，點(diǎn)和邊中肯定有元素的初值是負(fù)的.這個(gè)變形在研究平面圖的染色問(wèn)題時(shí)非常有用，因?yàn)槿绻硞€(gè)染色結(jié)果不成立，可以通過(guò)從初值為正的元素傳一些值給初值為負(fù)的元素，使得它們的值全部非負(fù)，這樣就使得歐拉公式不成立，從而導(dǎo)出矛盾.

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

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

?外平面圖：不包含K4和K2,3作為子式的圖. 外平面圖的頂點(diǎn)都與無(wú)窮外面關(guān)聯(lián).

?k-外平面圖：把外平面圖記作1-外平面圖.當(dāng)k≥2時(shí)，把k-外平面圖的無(wú)窮邊界上的點(diǎn)都刪除以后就得到(k-1)-外平面圖.

?k-邊界平面圖：頂點(diǎn)落在至多k個(gè)面的邊界上的平面圖叫k-邊界平面圖.顯然，外平面圖就是1-邊界平面圖.

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

2 平面圖的點(diǎn)染色

2.1 染色定義

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

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

?無(wú)圈點(diǎn)染色(Acyclic coloring): 對(duì)圖的一個(gè)正常點(diǎn)染色，如果任何兩個(gè)不同的顏色所染的點(diǎn)集合所導(dǎo)出的子圖是一個(gè)森林, 那么就稱此染色是無(wú)圈的；最小的顏色數(shù)稱為圖G的無(wú)圈點(diǎn)色數(shù)，記為a(G).

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

?(p,q)-標(biāo)號(hào)((p,q)-labelling)：相鄰的頂點(diǎn)的顏色至少差p，距離為2的兩個(gè)點(diǎn)的顏色至少差q. (1,0)-標(biāo)號(hào)就是我們說(shuō)的正常點(diǎn)染色.(1,1)-標(biāo)號(hào)又叫2-距離染色.

?鄰點(diǎn)可區(qū)別的點(diǎn)染色(Adjacent vertex distinguishing vertex coloring):任何相鄰的兩個(gè)點(diǎn)所對(duì)應(yīng)的鄰域的染色集合不同.

?鄰和可區(qū)別的點(diǎn)染色(Adjacent sum distinguishing vertex coloring): 任何相鄰的兩個(gè)點(diǎn)所對(duì)應(yīng)的鄰域的顏色之和不相等.

?r-色調(diào)染色(r-hued coloring):度數(shù)為d的頂點(diǎn)鄰域至少出現(xiàn)min{d,r}種顏色.

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

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

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

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

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

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

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

(2)對(duì)任意相鄰的兩個(gè)點(diǎn)u和v, 有|L(u)∩L(v)|≤d;

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

除了以上染色外，還考慮了把上述兩個(gè)概念相結(jié)合得到新的染色概念，如：均勻列表染色、無(wú)圈列表染色、鄰點(diǎn)(和)可區(qū)別的列表染色、圓點(diǎn)蔭度、列表分?jǐn)?shù)染色等.這些概念就不詳細(xì)地給出定義了.

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

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

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

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

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

?圖G不含長(zhǎng)度為4和9的圈，同時(shí)不含長(zhǎng)度為{5，6，7，8}中任兩數(shù)的圈[19].

?圖G不含長(zhǎng)度為3, 5, 6的圈[20].

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

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

?圖G不含長(zhǎng)度為3,7,8 的圈[23].

?圖G中兩個(gè)長(zhǎng)度至多為4的圈的距離至少為26[24].

?圖G不含長(zhǎng)度在4至8之間的圈[25].

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

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

?沒(méi)有3-圈.

?沒(méi)有4-圈.

?沒(méi)有5-圈和6-圈.

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

2.3 均勻點(diǎn)染色和均勻點(diǎn)蔭度

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年證明了如下著名的定理: 對(duì)于任意的正整數(shù)r，任意一個(gè)最大度至多為r的圖都存在一個(gè)均勻(r+1)-染色.對(duì)這一經(jīng)典結(jié)論，2008年Kierstead等[29]給出了一個(gè)簡(jiǎn)化的證明，同時(shí)也給出了一個(gè)找此均勻染色的多項(xiàng)式時(shí)間算法.另一方面，早在1973年Meyer猜想(ECC)(3)Meyer W. Equitable coloring. American Mathematical Monthly, 1973，80: 920-922.: 如果圖G不是Km,C2m+1, 那么存在一個(gè)r(≤Δ(G))使得G是均勻r-染色的.而Chen等[30]在1994年提出了一個(gè)加強(qiáng)版的猜想(EΔCC)：如果圖G不是Km,C2m+1,K2m+1,2m+1, 那么G存在一個(gè)均勻Δ(G)-染色， 即≡(G)≤Δ(G).并且證明了當(dāng)最大度Δ(G)≥3或者Δ(G)≥|G|/2時(shí)，該猜想是成立的.直到2012年Chen等[31]將結(jié)果改進(jìn)到了Δ(G)≥|G|/3+1.

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

2.4 無(wú)圈點(diǎn)染色

無(wú)圈點(diǎn)染色是在正常點(diǎn)染色的基礎(chǔ)上加強(qiáng)了限制：要求每個(gè)圈上都至少出現(xiàn)3種顏色.這個(gè)概念最早是由Grünbaum[36]提出的，同時(shí)他在文中證明了任意一個(gè)平面圖是無(wú)圈9-可染的.經(jīng)過(guò)了學(xué)者們的不斷改進(jìn)，最終Borodin[37]證明了任意一個(gè)平面圖是無(wú)圈5-可染的，并且證明了5是緊的上界. 這個(gè)結(jié)果被Mohar[38]推廣到了局部平面圖上了.Kostochka等[39]也構(gòu)造一個(gè)2-退化的二部平面圖，不是無(wú)圈4-可選的.而B(niǎo)orodin等[40]證明了對(duì)于不含三角形的平面圖，該結(jié)果可以改進(jìn)到4，對(duì)于圍長(zhǎng)至少為7的平面圖，可以改進(jìn)到3.從計(jì)算復(fù)雜度的角度來(lái)看，Kostochka[41]證明了判斷一個(gè)圖是否是無(wú)圈k-可染的(任給k≥3)，還是NP-完全的.

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

以下三個(gè)結(jié)果是非平面圖的.

?任意一個(gè)環(huán)面圖是無(wú)圈8-可選的[46].

?任意一個(gè)1-平面圖是無(wú)圈20-可染的[47].

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

2.5 點(diǎn)蔭度和線性點(diǎn)蔭度

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

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

3 平面圖的邊染色

3.1 邊染色方面的定義

圖G的線圖L(G)是指把G的邊集作為L(zhǎng)(G)的點(diǎn)集,L(G)中的兩個(gè)點(diǎn)相鄰當(dāng)且僅當(dāng)它們?cè)贕中的邊相鄰. 圖G的正常邊染色(Proper edge coloring)、無(wú)圈邊染色(Acyclic edge coloring)、強(qiáng)邊染色(Strong edge coloring)、(p,q)-邊標(biāo)號(hào)((p,q)-edge labelling)、 圓邊染色(Circular edge coloring)、 分?jǐn)?shù)邊染色(Fractional edge coloring)、(k,d)-邊可選的((k,d)-choosable)、列表邊染色(List edge coloring)、無(wú)圈列表邊染色(Acyclic list edge coloring)分別就是L(G)的正常點(diǎn)染色、無(wú)圈點(diǎn)染色、2-距離標(biāo)號(hào)、(p,q)-標(biāo)號(hào)、 圓染色、 分?jǐn)?shù)染色、(k,d)-可選的、列表邊染色和無(wú)圈列表邊染色.所用最小的顏色數(shù)稱為圖G的邊色數(shù)、無(wú)圈邊色數(shù)、強(qiáng)邊色數(shù)、(p,q)-邊標(biāo)號(hào)數(shù)、圓邊色數(shù)、分?jǐn)?shù)邊色數(shù)、(k,d)-邊可選數(shù)、列表邊色數(shù)和無(wú)圈列表邊色數(shù)，分別用′(G)、、和ac′list(G)表示.除以上邊染色外，人們還研究了如下邊方面的染色：

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

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

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

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

3.2 正常邊色數(shù)

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

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

?Δ=5且滿足以下條件之一：①不含4-圈或5-圈；②任意3-圈與4-圈不鄰；③每個(gè)點(diǎn)至多關(guān)聯(lián)一個(gè)三角形.

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

3.3 列表邊色數(shù)

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

?Δ≥12[32].

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

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

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

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

?Δ≥6且同時(shí)不含4-圈和6-圈.

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

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

同時(shí)對(duì)平面圖G，滿足充分條件如下：

?Δ≥8[57].

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

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

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

?Δ≤4[58].

3.4 無(wú)圈邊色數(shù)

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

3.5 強(qiáng)邊色數(shù)

因?yàn)閺?qiáng)邊色數(shù)一般比較大,想獲得強(qiáng)邊色數(shù)的確切值是非常困難的.Erd?s等[65]提出猜想:對(duì)任意圖G，當(dāng)Δ取偶數(shù)時(shí)，否則此猜想在Δ≤3的情況下是成立的.對(duì)最大度至少是3平面圖, 一般的界是:下面主要介紹平面圖的一些其他結(jié)果：

3.6 均勻邊色數(shù)

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

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

3.7 鄰點(diǎn)(和)可區(qū)別邊色數(shù)

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

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

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

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

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

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

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

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

4 平面圖的全染色

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

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

?Δ(G)≥8且對(duì)G中任一頂點(diǎn)x,都存在整數(shù)k∈{3,4,5,6,7,8}使x至多關(guān)聯(lián)一個(gè)k-圈.

?Δ(G)≥8且對(duì)G中任一頂點(diǎn)x,都存在兩整數(shù)i,j∈{3,4,5,6}使任意兩個(gè)經(jīng)過(guò)x的長(zhǎng)度為i和j的圈都不相鄰.

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

?Δ(G)≥7且對(duì)G中任一頂點(diǎn)x, 都存在整數(shù)k∈{3,4,5,6,7,8}使x不關(guān)聯(lián)任一個(gè)k-圈.

?Δ(G)≥7且對(duì)G中任一頂點(diǎn)v, 都存在整數(shù)iv∈{3,4,5,6}使v不在任一個(gè)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沒(méi)有4-圈和6-圈.

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

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

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

關(guān)于圖G的列表全色數(shù)有猜想：如果G是一個(gè)簡(jiǎn)單圖，則″(G)[56]. 這確實(shí)是一個(gè)非常有挑戰(zhàn)性的猜想，目前對(duì)一般圖的結(jié)果非常之少. 關(guān)于平面圖，有兩類結(jié)果. 一類是關(guān)于的，它需要有如下條件之一：

?Δ(G)≥9[90].

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

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

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

?Δ(G)≥12[56].

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

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

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

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

4.2 鄰點(diǎn)(和)可區(qū)別的全染色

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

Δ(G)+1≤

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

Δ(G)+1≤

4.3 無(wú)圈全染色

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

5 與平面圖的面有關(guān)的染色

下面的三個(gè)染色因?yàn)橐獙?duì)平面圖的面進(jìn)行染色，它們是平面圖的專屬染色：①平面圖的點(diǎn)面染色：對(duì)平面圖的點(diǎn)和面進(jìn)行染色，使得相鄰的點(diǎn)、相鄰的面、相關(guān)聯(lián)的點(diǎn)和面之間都染不同的顏色.所用最少的顏色數(shù)稱為平面圖的點(diǎn)面色數(shù)，記為vf(G)； ②平面圖的邊面染色: 對(duì)平面圖的邊和面進(jìn)行染色，使得相鄰的邊、相鄰的面、相關(guān)聯(lián)的邊和面之間都染不同的顏色.所用最少的顏色數(shù)稱為平面圖的邊面色數(shù)，記為ef(G)； ③平面圖的點(diǎn)邊面染色: 對(duì)平面圖的點(diǎn)、邊和面進(jìn)行染色，使得任何兩個(gè)相鄰或相關(guān)聯(lián)的元素之間都染不同的顏色.所用最少的顏色數(shù)稱為平面圖的點(diǎn)邊面色數(shù)，也叫完備色數(shù)，記為vef(G). 人們已經(jīng)證明了：對(duì)任何平面圖G，vf(G)≤6,ef(G)≤Δ(G)+3,vef(G)≤Δ(G)+4. 其他結(jié)果參見(jiàn)文獻(xiàn)[7].

6 可以繼續(xù)探討的一些問(wèn)題

今后可以繼續(xù)研究的問(wèn)題：

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

(2)考慮多種染色的組合，研究新的染色，獲得比現(xiàn)有結(jié)果更一般的結(jié)果，例如，可以在考慮鄰和可區(qū)別的邊染色時(shí)要求相鄰兩點(diǎn)的色和至少差k(k>0)，或者在正常染色的基礎(chǔ)上再要求增加一條邊兩個(gè)端點(diǎn)所關(guān)聯(lián)的邊中至多有k個(gè)相同色，等等.

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

后記： 限于篇幅，還有許多關(guān)于平面圖的染色方面的結(jié)果沒(méi)有列出，它們都是很有價(jià)值的，例如：圓染色(Circular coloring)、 多重染色(Multiple coloring)、分?jǐn)?shù)染色(Fractional coloring)、適應(yīng)點(diǎn)染色(Adaptive coloring)、對(duì)策染色(Game coloring)、DP-染色(DP-coloring),等等.另外，本文列出的一些結(jié)果也沒(méi)有標(biāo)出出處，讀者可以從主要結(jié)果的被引處找到它們，在此謹(jǐn)向這些論文的作者們表示深深的歉意.