極大平面圖的結(jié)構(gòu)與著色理論(3)純樹著色與唯一4-色極大平面圖猜想

許 進

?

極大平面圖的結(jié)構(gòu)與著色理論(3)純樹著色與唯一4-色極大平面圖猜想

許 進*

(北京大學(xué)高可信軟件技術(shù)教育部重點實驗室 北京 100871)(北京大學(xué)信息科學(xué)技術(shù)學(xué)院 北京 100871)

一個極大平面圖若是從出發(fā)，不斷地在三角面上嵌入3度頂點得到的，則稱此極大平面圖為遞歸極大平面圖。唯一4-色極大平面圖猜想是指：一個平面圖是唯一4-可著色的當且僅當它是遞歸極大平面圖。此猜想已有43年歷史，是圖著色理論中繼四色猜想之后另一個著名的未解猜想。為此，該文相繼深入研究了啞鈴極大平面圖與遞歸極大平面圖的結(jié)構(gòu)與特性，結(jié)合該系列文章(2)的擴縮運算，給出了證明唯一4-色極大平面圖猜想的一種思路。

唯一4-色極大平面圖猜想；純樹著色猜想；啞鈴極大平面圖；遞歸極大平面圖

1 引言

圖論誕生于1736年EULER研究的哥尼斯堡七橋問題，以及1847年KIRCHHOFF研究的電網(wǎng)絡(luò)問題。圖論在最近70年來得以迅速發(fā)展，其主要原因有兩個：一個是受到電子計算機發(fā)展的影響；另一個更重要的原因是受四色猜想的影響。對四色猜想的研究推動了整個圖論學(xué)科的發(fā)展，開創(chuàng)了圖論的許多領(lǐng)域，諸如拓撲圖論、最大獨立集與最大團理論、頂點與邊覆蓋理論、色多項式理論、Tutte-多項式理論、因子理論、整數(shù)流理論，特別是圖著色理論等。

在圖著色領(lǐng)域，除著名的四色猜想外，相繼出現(xiàn)了其它不少著名的猜想，本文所討論的“唯一4-色極大平面圖猜想”就是其中之一。唯一4-色極大平面圖猜想源于1973年GREENWELL與KRONK所提出的猜想[1]，距今已有43年，此猜想本質(zhì)上也與四色猜想有內(nèi)在聯(lián)系，至今尚未解決。

圖的唯一著色概念是由GLEASON和CARTWRIGHT[2], CARTWRIGHT和HARARY[3]相繼提出的。CARTWRIGHT和HARARY給出了一些判定標號圖是唯一可著色圖的充分條件。其后，許多學(xué)者在此領(lǐng)域做了大量工作，諸如HARARY, HEDETNIEMI和ROBINSON[4]研究了唯一-可著色圖的連通性問題、邊數(shù)的取值問題等；對于任意，不含的唯一-色圖是否存在這個問題，眾多學(xué)者展開了研究。如NESTRIL[5,6]研究了臨界-唯一可著色圖的性質(zhì)，并證明了存在不含三角形的唯一可著色圖；1974年，GREENWELL和LOVASZ[7]證明了存在不含短奇圈的唯一-可著色圖；1975年，MULLER[8]解決了此問題的一般情形(也見文獻[9])，即對任意的正整數(shù)和，存在圍長大于的唯一-可著色圖，其中MULLER采用的也是構(gòu)造的方法；MULLER[8,9], AKSIONOV[10], MELNIKOV 與 STEINBERG[11]研究了邊-臨界唯一可著色圖性質(zhì)；WANG和ARTZY[12]得到了“當，如果存在一個不含的唯一-可著色圖，那么圖的邊數(shù)嚴格大于”；OSTERWEIL[13]給出6-團環(huán)構(gòu)造一類唯一3-可著色圖的方法；BOLLOBAS和SAUER[14]證明了“對任意和，總存在一個圍長至少為的唯一-可著色圖”，其中是給定圖的圍長，并證明了“對任意和，總存在一個階數(shù)至少為的臨界-唯一-色圖”；DMITRIEV[15]推廣了BOLLOBAS在文獻[16]中的結(jié)果；XU[17]證明了“如果是一個頂點數(shù)為，邊數(shù)為的唯一-可著色圖，則，且該界是最好可能的”，并猜想“如果是一個頂點數(shù)為，邊數(shù)為的唯一-可著色圖，則含子圖”。同時，CHAO和CHEN[18]證明了“對每個正整數(shù)，存在一個不含三角形的-階唯一3-可著色圖”；AKBARI, MIRROKNI和SADJAD[19]證明了“存在階數(shù)為24不含三角形的唯一3-可著色圖且邊數(shù)，其中”，該結(jié)果否定了XU[17]的猜想。

在邊唯一可著色圖方面，1973年，GREENWELL與KRONK首先研究了唯一邊-可著色圖[1]。他們提出了下述猜想：

1975年，F(xiàn)IORINI[20]獨立研究了邊唯一可著色問題，并獲得一些與GREENWELL及KRONK[1]類似結(jié)果。其后，不少學(xué)者研究了唯一邊可著色問題，如THOMASON[21,22], FIORINI與WILSON[23], ZHANG[24], GOLDWASSER與ZHANG[25,26], KRIESSEL[27]等。

1977年，F(xiàn)IORINI和WILSON[23], 及FISK[28]分別獨立提出下述猜想：

猜想2 每個至少有4個頂點的唯一3-邊可著色立方平面圖含一個三角形。

這個猜想是在猜想1的基礎(chǔ)上進一步提出來的。FOWLER[29]也對此猜想進行了一定的研究。此猜想至今未被解決。

在唯一可著色平面圖方面，1969年，CHARTRAND和GELLER[30]開始研究唯一可著色平面圖。他們證明了至少有4個頂點的唯一3-可著色平面圖至少含兩個三角形，唯一4-可著色平面圖是極大平面圖，不存在唯一5-可著色平面圖。

唯一3-色平面圖的充分必要條件是什么？這個問題至今尚未解決，但關(guān)于唯一3-色平面圖的一些基本特性已有很多研究。1977年，AKSIONOV[31]證明了階數(shù)的唯一3-色平面圖至少包含3個三角形，并詳細刻畫了恰含3個三角形的唯一3-色平面圖的結(jié)構(gòu)特征。同年，MELNIKOV和STEINGERG[11]研究了邊臨界唯一3-色平面圖，并提出如下問題：找出-階邊臨界唯一3-可著色平面圖邊數(shù)的精確上界。2013年，MATSUMOTO[32]證明了；最近，LI等人[33,34]證明了，其中，并證明了包含至多4個三角形的唯一3-色平面圖中存在相鄰三角形。

哪些極大平面圖是唯一4-可著色的？換言之，唯一4-可著色平面圖的基本特征是什么？這個問題自然是研究唯一4-可著色平面圖的主要內(nèi)容。圍繞此問題，許多學(xué)者從不同方面展開了研究。

其實，F(xiàn)ISK在文獻[28]中，也提出了與猜想2等價的猜想3。

猜想3與猜想2的等價性是容易證明的，且是猜想1的特殊情況。1998年，BOHME, STIEBITZ 和 VOIGT[35]證明了猜想3的最小反例圖是5-連通的。我們把猜想3稱為唯一4-色極大平面圖猜想。

對于一個平面圖，如果只要任何兩個不相鄰的頂點之間再加一條邊，其平面性一定被破壞，則稱該平面圖為極大平面圖。若一個平面圖的每個面（包括無窮面）都由3條邊組成，則稱該平面圖為三角剖分圖。易證，極大平面圖和三角剖分圖是等價的。

文中未給出的概念與符號可查看文獻[38,39]。

2 樹著色與圈著色

3 純樹著色極大平面圖

由第2節(jié)知，極大平面圖可分為純樹著色型，純?nèi)χ团c混合著色型3種。而刻畫這3種類型極大平面圖的結(jié)構(gòu)，給出相應(yīng)的充分必要條件是很困難的問題。如若刻畫出純樹著色型的結(jié)構(gòu)特征，

圖1 一個11-階4-色極大平面圖的全部4種著色

自然也就證明了已有43年的唯一4-色極大平面圖猜想(猜想3)。故從本文開始，我們將逐漸對這3種類型極大平面圖展開研究。本節(jié)重點針對純樹著色型展開研究。

3.1 最小度為5的純樹著色極大平面圖猜想

文獻[41]中已指出：正二十面體是一個最小度為5的純樹著色極大平面圖，它共有10種不同的樹著色，如圖2所示。

猜想4 最小度為5的極大平面圖是純樹著色

的當且僅當它是正二十面體。

3.2 啞鈴極大平面圖

3.2.1啞鈴變換 啞鈴變換的對象圖是一個全封啞鈴，即為一個4-輪，如圖3所示。所謂啞鈴變換，是指按照如下步驟，將一個全封啞鈴變成一個如圖3(a)，或圖3(b)中最右邊所示構(gòu)形的過程：

步驟 1 將輪心劃開，橫劃或豎劃，如圖3(a)，或圖3(b)中的第2個圖示；

步驟2 伸展開成如圖3(a)，或圖3(b)中所示的第3個圖；

步驟3 在6-圈內(nèi)添加2-長路，并按橫劃開與豎劃開，令2-長路與6-圈連接邊構(gòu)成如圖3中的最右邊的構(gòu)形。

上述步驟的逆運算稱為啞鈴收縮變換，并把圖

圖2 正二十面體及它的全部10種4-著色

圖3 啞鈴變換對象圖及過程示意圖

3(a)中最右邊的構(gòu)形稱為啞鈴收縮變換對象圖。啞鈴變換實際上是擴334-輪運算，可參見圖3(c)，也可參見文獻[39]。

由此定義可知，對一個啞鈴極大平面圖實施啞鈴變換后所得之圖必為啞鈴極大平面圖。

3.2.3 啞鈴極大平面圖的性質(zhì) 下面，我們進一步討論啞鈴極大平面圖的一些性質(zhì)。

定理1 (1)任一啞鈴極大平面圖恰有3個4-度頂點；(2)每個啞鈴極大平面圖的階數(shù)為，其中；(3)每個啞鈴極大平面圖均為純樹著色型，且每個-階啞鈴極大平面圖恰有種不同的著色。

(3)用數(shù)學(xué)歸納法來證明：9-階啞鈴極大平面圖時結(jié)論成立，13-階的啞鈴極大平面圖共有4種著色，且均為純樹著色，如圖5所示。故結(jié)論成立。

圖4 階數(shù)最小的4個啞鈴極大平面圖

圖5 13-階啞鈴極大平面圖的所有4種著色

圖6 頂點賦色的啞鈴變換與啞鈴收縮變換

色不變的情況下，恰有兩種著色，如圖6(a)與6(c)所示。故中恰含有種不同的著色。從而本定理獲證。

3.2.4 啞鈴極大平面圖的計數(shù) 9-階啞鈴極大平面圖僅有1個，由于它的3個4-輪是等同的，因而，13-階的啞鈴極大平面圖也只有1個；在對9-階極大平面圖實施啞鈴變換時，由于只對其中一個實施啞鈴變換，故其余兩個是等同的，從而導(dǎo)致在13-階啞鈴極大平面圖中，它的3個4-輪中有兩個是等同的，由此推出17-階啞鈴極大平面圖共有2個，分別如圖4(c), 4(d)所示。進而，關(guān)于一般階數(shù)的啞鈴極大平面圖，我們有

證明見文獻[41]。

4 遞歸極大平面圖

除四色猜想外，唯一4-色極大平面圖猜想已有43年的歷史，業(yè)已成為圖著色理論中一個很有影響的猜想。而此猜想的對象是遞歸極大平面圖，故在本節(jié)對此類圖進行深入地研究。

基本性質(zhì)

定理4 (1)不存在恰有2個相鄰的3-度頂點的極大平面圖；(2)不存在恰有3個兩兩相鄰的3-度頂點的極大平面圖。

圖7 頂點數(shù)分別為4, 5, 6的3個遞歸極大平面圖

圖8 定理4證明的示意圖

(2)只有1個3-度頂點；

(3)只有2個3-度頂點；

(4)只有3個3-度頂點。

對于第1種情況顯然結(jié)論成立；而由定理4知第3, 4種情況不存在。故只考慮第2種情況。即在子圖中只存在一個3-度頂點，記作。令，類似于上述分析方法，若，則結(jié)論得證；否則，必恰有一個3-度頂點。如此下去，在有限步內(nèi)，必有；否則，當只含有4個頂點時只能同構(gòu)于，從而說明圖是遞歸極大平面圖，但只有一個3-度頂點，與定理3矛盾！故本定理獲證。

4.2 (2,2)-遞歸極大平面圖

本小節(jié)引入一類特殊的遞歸極大平面圖：(2,2)-遞歸極大平面圖，并研究它的相關(guān)性質(zhì)。一個遞歸極大平面圖稱為(2,2)-遞歸極大平面圖，如果中只有2個度數(shù)為3的頂點，且這兩個頂點之間的距離為2。容易證明5-階(2,2)-遞歸極大平面圖只有1個，如圖9(a)所示，6-階(2,2)-遞歸極大平面圖也只有1個，如圖9(b)所示。

圖9 5-階及6-階(2,2)-遞歸極大平面圖

為了弄清(2,2)-遞歸極大平面圖的結(jié)構(gòu)，我們先將4-階完全圖分成3個區(qū)，并給出相應(yīng)頂點的名稱，由頂點標定的三角形稱為外三角形，頂點稱為中心頂點或簡稱為中心點，如圖10所示。我們約定：頂點著色為顏色2，頂點著顏色3，頂點著顏色4，頂點著顏色1，稱這4個頂點與對應(yīng)的著色為(2,2)-遞歸極大平面圖的色坐標系中的基本坐標軸。4個色坐標軸分別為(顏色1)，(顏色2)，(顏色3)，(顏色4)。

顯然，沒有4-階(2,2)-遞歸極大平面圖；不同構(gòu)的5-階(2,2)-遞歸極大平面圖只有1個，就是在如圖10所示的Ⅰ區(qū)、Ⅱ區(qū)或Ⅲ區(qū)中通過嵌入一個3-度頂點的運算(即擴3-輪運算)而得到。不失一般性，我們約定，所增加的頂點在Ⅱ區(qū)。因而該頂點著色為顏色2(見圖9(a))；6-階不同構(gòu)的(2,2)-遞歸極大平面圖也只有1個(如圖9(b)所示)，因為在5-階極大平面圖的任意面內(nèi)嵌入一個3-度頂點所得到的6-階極大平面圖均是同構(gòu)的。故這里約定：在由頂點這3個頂點構(gòu)成的面上(即在Ⅱ區(qū)的子Ⅰ區(qū))嵌入第6個頂點，顯然，它著色為顏色4，如圖9(b)

圖10 色坐標系的基本框架圖

所示。不失一般性，在此進一步約定更高階數(shù)的(2,2)-遞歸極大平面圖只在Ⅰ區(qū)和Ⅱ區(qū)內(nèi)有頂點，在Ⅲ區(qū)內(nèi)無頂點。

在上述約定的基礎(chǔ)上，現(xiàn)在來討論(2,2)-遞歸極大平面圖的分類。有兩種分類方法：

第1種方法是按照嵌入3-度頂點的區(qū)來分類：(1)只在Ⅱ區(qū)通過不斷嵌入3-度頂點而得到的(2,2)-遞歸極大平面圖，如圖11所示的3個圖均是此種類型；(2)通過不斷地在Ⅰ區(qū)和Ⅱ區(qū)之間隨機地嵌入3-度頂點而得到，如圖12所示。對于極大平面圖，有如下結(jié)論。

命題1 極大平面圖的任一面均可成為無窮面。

圖11 只在Ⅱ區(qū)嵌入3-度頂點的(2,2)-遞歸極大平面圖

圖12 在Ⅰ區(qū)與Ⅱ區(qū)之間隨機嵌入3-度

頂點的(2,2)-遞歸極大平面圖

由命題1可知，在上述Ⅰ區(qū)與Ⅱ區(qū)之間隨機嵌入3-度頂點的(2,2)-遞歸極大平面圖中，可以將Ⅰ區(qū)或者Ⅱ區(qū)中的任一3-度頂點變換到外三角形面上，就等價于分類中的(1)的情況，即只在Ⅱ區(qū)通過不斷地嵌入3-度頂點而得到的(2,2)-遞歸極大平面圖。因此，只需考慮在Ⅱ區(qū)通過不斷嵌入3-度頂點而得到的(2,2)-遞歸極大平面圖即可。

第2種分類方法是根據(jù)2個3-度頂點所在長度為2路中的3個頂點是否存在一個公共的相鄰頂點來進行分類：若存在，則稱為相鄰型，否則稱為非相鄰型。如圖11(a)是相鄰型的，而圖11(b), 11(c)均是非相鄰型的。

由圖9(a)可以看出，5-階(2,2)-遞歸極大平面圖是一個雙心輪圖，且每個輪心的鄰域中頂點度數(shù)均為4，但當階數(shù)時，有下述結(jié)論。其中雙心輪圖是指一個圈與兩個孤立點的聯(lián)圖構(gòu)成的極大平面圖。

證明 (1)采用數(shù)學(xué)歸納法。由于階數(shù)為5的極大平面圖只有一個(如圖9(a)所示)，它是一個雙心輪圖，故每個三角形面是等同的。因此，同構(gòu)意義下的6-階遞歸極大平面圖只有一個，且該遞歸極大平面圖是(2,2)-遞歸極大平面圖(如圖9(b)所示)。該圖中的兩個3-度頂點的鄰域中均恰有一個頂點的度數(shù)等于4，其余頂點的度數(shù)均，這就證明了當頂點數(shù)時結(jié)論成立。

(2)和(3)可通過在逐步構(gòu)造(2,2)-遞歸極大平面圖的過程中獲證。

4.3 擴4-輪運算圖的著色

色來選擇該頂點嵌入的三角面。

面圖是圖13中所示的第3行第2個圖。

關(guān)于(2,2)-遞歸極大平面圖的色序列，容易得到下述結(jié)論：

下面討論擴4-輪運算在(2,2)-遞歸極大平面圖類中頂點著色問題。我們知道，對一個給定的(2,2)-遞歸極大平面圖，它是唯一4-可著色的，且每個頂點所著的顏色也是確定的。

圖13 7至9-階的所有11個(2,2)-遞歸極大平面圖

5 唯一4-色極大平面圖的證明思路

唯一4-色極大平面圖猜想是一個尚待解決的難題，該猜想的對象是遞歸極大平面圖，故在第4節(jié)中對此類圖的性質(zhì)展開了詳細討論，我們在文獻[41]中提出了純樹著色猜想，并指出若此猜想成立，則唯一4-色極大平面圖猜想成立。特別在本文第3節(jié)中重點針對啞鈴極大平面圖進行了深入研究。本節(jié)給出的唯一4-色極大平面圖猜想證明思路實際上是證明純樹著色極大平面圖猜想。

下面，給出純樹著色猜想的證明思路，即按照如下9種情況，逐一給出證明：

有興趣的讀者可參見文獻[39]中的3.4節(jié)，特別是圖17。關(guān)于這方面的詳細論述將在本系列后續(xù)文章中給出。

6 結(jié)束語

我們在文獻[41]中所提出的純樹著色猜想是：“一個極大平面圖是純樹著色的充分必要條件是是正二十面體或啞鈴極大平面圖”，并指出：若純樹著色猜想成立，則唯一4-色極大平面圖猜想成立。故本文的另一個主要內(nèi)容是研究啞鈴極大平面圖結(jié)構(gòu)與性質(zhì)。

本文所提出的唯一4-色極大平面圖猜想的證明思路實際上是給出證明純樹著色猜想的思路。該證明思路是：在假設(shè)是純樹著色極大平面圖的基礎(chǔ)上，基于文獻[39]中所給出的擴縮運算法，以及任意()-階最小度的極大平面圖要么有父代圖，要么有祖父圖，我們給出了證明純樹著色猜想的9種情況，其中8種情況是否定的，只有一種情況是肯定的。

本文的工作為證明純樹著色猜想奠定了一定的基礎(chǔ)。在本系列后續(xù)文章中，我們將給出4-色極大平面圖的擴縮運算系統(tǒng)，簡稱為色擴縮運算系統(tǒng)。然后在此基礎(chǔ)上，純樹著色猜想有望得到完整的證明。

致謝 本文在完成過程中，與姚兵教授、陳祥恩教授以及吳建良教授，以及我的5位圖論專業(yè)學(xué)生：周洋洋(碩士生)，李澤鵬(博士后)，劉小青(博士生)，朱恩強(博士后)以及王宏宇(博士生)等進行了多次有益討論，在此表示感謝。最后，特別感謝北京大學(xué)的何新貴院士、余道衡教授對本文的審閱、以及對作者的鼓勵、鞭策與支持。

[1] GREENWELL D and KRONK H V. Uniquely line-colorable graphs[J]., 1973, 16(4): 525-529. doi: 10.4153/CMB-1973-086-2.

[2] GLEASON T C and CARTWRIGHT F D. A note on a matrix criterion for unique colorability of assigned graph[J]., 1967, 32(3): 291-296. doi: 10.1007/ BF02289592.

[3] CARTWRIGHT F D and HARARY F. On the coloring of signed graphs[J]., 1968, 23(4): 85-89.

[4] HARARY F, HEDETNIEMI S T, and ROBINSON R W. Uniquely colorable graphs[J]., 1969, 6(3): 264-270. doi: 10.1016/S0021-9800(69) 80086-4.

[5] NESTRIL J. On critical uniquely colorable graphs[J]., 1972, 23(1): 210-213. doi: 10.1007/ BF01304871.

[6] NESTRIL J. On uniquely colorable graphs without short cycles[J]., 1973, 98(2): 122-125.

[7] GREENWELL D and LOVASZ L. Applications of product coloring[J]., 1974, 25(3): 335-340. doi: 10.1007/BF01886093.

[8] MULLER V. On colorable critical and uniquely colorable critical graphs[J]., 1974: 385-386.

[9] MULLER V. On coloring of graphs without short cycles[J]., 1979, 26(2): 165-176. doi: 10.1016/ 0012-365X(79)90121-3.

[10] AKSIONOV V A. Chromatically connected vertices in planar graphs[J]., 1977, 31(31): 5-16.

[11] MELNIKOV L S and STEINBERG R. One counterexample for two conjectures on three coloring[J]., 1977, 20(77): 203-206. doi: 10.1016/0012-365X (77)90059-0.

[12] WANG C C and ARTZY E. Note on the uniquely colorable graphs[J].,, 1973, 15(2): 204-206. doi: 10.1016/0095-8956(73)90022-1.

[13] OSTERWEIL L J. Some classes of uniquely 3-colorable graphs[J]., 1974, 8(1): 59-69. doi: 10. 1016/0012-365X(74)90110-1.

[14] BOLLOBAS B and SAUER N W. Uniquely colorable graphs with large girth[J]., 1976, 28(6): 1340-1344. doi: 10.4153/CJM-1976-133-5.

[15] DMITRIEV I G. Weakly cyclic graphs with integral chromatic spectra[J]., 1980, 34(34): 3-7.

[16] BOLLOBAS B. Uniquely colorable graphs[J].,, 1978, 25(1): 54-61. doi: 10.1016/S0095-8956(78)80010-0.

[17] XU S J. The size of uniquely colorable graphs[J].,, 1990, 50(2): 319-320. doi: 10.1016/0095-8956(90)90086-F.

[18] CHAO C and CHEN Z. On uniquely 3-colorable graphs[J]., 1993, 112(1): 21-27. doi: 10.1016/0012- 365X(93)90220-N.

[19] AKBARI S, MIRROKNI V S, and SADJAD B S.-free uniquely vertex colorable graphs with minimum possible edges[J].,, 2001, 82(2): 316-318. doi: 10.1006/jctb.2000.2028.

[20] FIORINI S. On the chromatic index of a graph, III: Uniquely edge-colorable graphs[J]., 1975, 26(3): 129-140.

[21] THOMASON A G. Hamiltonian cycles and uniquely edge colorable graphs[J]., 1978, 3: 259-268. doi: 10.1016/S0167-5060(08)70511-9.

[22] THOMASON A G. Cubic graphs with three Hamiltonian cycles are not always uniquely edge Colorable[J]., 1982, 6(2): 219-221. doi: 10.1002/jgt. 3190060218.

[23] FIORINI S and WILSON R J. Edge colouring of graphs[J]., 1977, 23(1): 237-239.

[24] ZHANG C Q. Hamiltonian weights and unique edge-3- colorings of cubic graphs[J]., 1995, 20(1): 91-99. doi: 10.1002/jgt.3190200110.

[25] GOLDWASSER J L and ZHANG C Q. On the minimal counterexamples to a conjecture about unique edge-3- coloring[J]., 1996, 113: 143-152.

[26] GOLDWASSER J L and ZHANG C Q. Uniquely edge- colorable graphs and Snarks[J]., 2000, 16(3): 257-267. doi: 10.1007/PL00007221.

[27] KRIESELL M. Contractible non-edges in 3-connected graphs [J].,, 1998, 74(2): 192-201. doi: 10.1006/jctb.1998.1842.

[28] FISK S. Geometric coloring theory[J]., 1977, 24(3): 298-340. doi: 10.1016/0001- 8708(77)90061-5.

[29] FOWLER T. Unique coloring of planar graphs[D]. [Ph. dissertation], Georgia Institute of Technology, 1998: 19-55.

[30] CHARTRAND G and GELLER D. On uniquely colorable planar graphs[J]., 1969, 6(3): 271-278. doi: 10.1016/S0021-9800(69)80087-6.

[31] AKSIONOV V A. On uniquely 3-colorable planar graphs[J]., 1977, 20(3): 209-216. doi: 10.1016/ 0012-365X(77)90061-9.

[32] MATSUMOTO N. The size of edge-critical uniquely 3-colorable planar graphs[J]., 2013, 20(4): 1823-1831.

[33] LI Z P, ZHU E Q, SHAO Z H,. Size of edge-critical uniquely 3-colorable planar graphs[J]., 2016, 339(4): 1242-1250. doi: 10.1016/j.disc.2015.11.009.

[34] LI Z P, ZHU E Q, SHAO Z H,. A note on uniquely 3-colorable planar graphs[J]., 2016: 1-8. doi: 10.1080/00207160. 2016.1167196.

[35] BOHME T, STIEBITZ M, VOIGT M,. On uniquely 4-colorable planar graphs[OL]. url=cite-seer.ist.psu.edu/ 110448.html.1998.

[36] DAILEY D P. Uniqueness of colorability and colorability of

planar 4-regular graphs are NP-complete[J].

[37] XU J and WEI X S. Theorems of uniquely-colorable graphs[J].(), 1995, 23: 59-62.

[38] BONDY J A and MURTY U S R. Graph Theory[M]. Springer, 2008: 6-58.

[39] 許進. 極大平面圖的結(jié)構(gòu)與著色理論: (2)多米諾構(gòu)形與擴縮運算[J]. 電子與信息學(xué)報, 2016, 38(6): 1271-1327. doi: 10.11999/JEIT160224.

XU Jin. Theory on the structure and coloring of maximal planar graphs(2): Domino configurations and extending- contracting operations[J].&, 2016, 38(6): 1271-1327. doi: 10.11999/JEIT160224.

[40] ZHU E Q, LI Z P, SHAO Z H,. Acyclically 4-colorable triangulations[J]., 2016, 116(6): 401-408. doi: 10.1016/j.ipl.2015.12.005.

[41] XU J, LI Z P, and ZHU E Q. On purely tree- colorable planar graphs[J]., 2016, 116(8): 532-536. doi: 10.1016/j.ipl.2016.03.011.

許 進： 男，1959年生，教授，主要研究領(lǐng)域為圖論與組合優(yōu)化、生物計算機、社交網(wǎng)絡(luò)與信息安全等.

Foundation Items: The National 973 Program of China (2013CB 329600), The National Natural Science Foundation of China (61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437)

Theory on Structure and Coloring of Maximal Planar Graphs(3) Purely Tree-colorable and Uniquely 4-colorable Maximal Planar Graph Conjectures

XU Jin

(Key Laboratory of High Confidence Software Technologies, Peking University, Beijing 100871, China)(School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China)

A maximal planar graph is called the recursive maximal planar graph if it can be obtained fromby embedding a 3-degree vertex in some triangular face continuously. The uniquely 4-colorable maximal planar graph conjecture states that a planar graph is uniquely 4-colorable if and only if it is a recursive maximal planar graph. This conjecture, which has 43 years of history, is a very influential conjecture in graph coloring theory after the Four-Color Conjecture. In this paper, the structures and properties of dumbbell maximal planar graphs and recursive maximal planar graphs are studied, and an idea of proving the uniquely 4-colorable maximal planar graph conjecture is proposed based on the extending-contracting operation proposed in this series of article (2).

Uniquely 4-colorable maximal planar graph conjecture; Purely tree-colorable planar graph conjecture; Dumbbell maximal planar graphs; Recursive maximal planar graphs

O157.5

A

1009-5896(2016)06-1328-26

10.11999/JEIT160409

Mathematics, 1980, 30(3): 289-293. 10.1016/0012- 365X(80)90236-8.

2016-04-22；改回日期：2016-04-26；網(wǎng)絡(luò)出版：2016-05-05

許進 jxu@pku.edu.cn

國家973規(guī)劃項目(2013CB329600)，國家自然科學(xué)基金(61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437)