唯一可著色圖研究進(jìn)展

(蘭州大學(xué) 信息科學(xué)與工程學(xué)院， 甘肅 蘭州 730000)

1 引言及預(yù)備知識(shí)

設(shè)G=(V,E)是一個(gè)無(wú)向簡(jiǎn)單圖.圖G的一個(gè)k-著色是指從G的頂點(diǎn)集V到顏色集 {1,2,…,k}的映射c，滿足對(duì)任意的uv∈E，有c(u)≠c(v). 圖G是k-可著色的，如果G有一個(gè)k-著色.圖G的色數(shù)，記作(G)，是指使得G為k-可著色的最小正整數(shù)k.若(G)=k，則稱G是k-色圖.顯然，圖G的每個(gè)k-著色c可以看作是對(duì)頂點(diǎn)集V的一個(gè)劃分 {V1,V2,…,Vk}，其中，Vi表示分配到顏色i的所有頂點(diǎn)構(gòu)成的集合，i=1,2,…,k. 稱集合Vi為著色c的色類(lèi).易驗(yàn)證，每個(gè)Vi是圖G的獨(dú)立集.

圖G的兩個(gè)k-著色c與c′稱為是等價(jià)的，如果由這兩種著色導(dǎo)出的V的無(wú)序劃分是相同的.圖G稱為唯一k-可著色的，如果(G)=k，且G的任意兩個(gè)k-著色是等價(jià)的. 也就是說(shuō)，在不考慮顏色置換的情況下，G只有一個(gè)k-著色.可看出，唯一k-可著色圖G的所有k-著色導(dǎo)出的V的無(wú)序劃分是相同的.例如，完全圖Kn是唯一n-可著色圖.

此外，唯一可著色圖可根據(jù)其色多項(xiàng)式來(lái)定義.設(shè)P(G,x)為圖G的色多項(xiàng)式，則G是唯一k-可著色圖當(dāng)且僅當(dāng)P(G,k)=k!，關(guān)于圖的色多項(xiàng)式的研究可參見(jiàn)文獻(xiàn)[1-3].

圖的唯一可著色問(wèn)題最早是由Chartwright等[4]在研究符號(hào)圖的著色時(shí)提出的(符號(hào)圖唯一可著色的研究可參見(jiàn)文獻(xiàn)[5]).隨后，一般圖的唯一可著色問(wèn)題[6]以及平面圖的唯一可著色問(wèn)題[7]都有了研究.

圖的唯一可著色問(wèn)題與經(jīng)典的圖著色問(wèn)題研究的側(cè)重點(diǎn)有所不同.經(jīng)典的圖著色問(wèn)題主要在刻畫(huà)給定圖的色數(shù)，而唯一可著色問(wèn)題主要判斷哪些圖是唯一可著色的.

根據(jù)唯一可著色的定義，知道并不是所有的圖是唯一可著色的.1980 年，Dailey[8]證明了對(duì)任意圖G，判斷G是否為唯一可著色圖的問(wèn)題是NP-完全的.因此，關(guān)于唯一可著色圖的研究主要集中在結(jié)構(gòu)特征、存在性以及構(gòu)造等方面.

本文主要介紹唯一可著色圖研究的重要結(jié)論，特別是唯一3-可著色平面圖的相關(guān)結(jié)果.文中未給出的定義及符號(hào)，請(qǐng)參照文獻(xiàn)[9].

2 唯一可著色圖的性質(zhì)

1968年，Chartwrigh等[4]初步刻畫(huà)了唯一可著色圖的特征，得到如下定理：

定理2.1[4]若G是一個(gè)唯一k-可著色圖，則在G的每個(gè)k-著色下，G中任意兩個(gè)色類(lèi)導(dǎo)出的子圖是連通的.

1969年，Harary等[6]進(jìn)一步得到了唯一k-可著色圖G的一些基本性質(zhì)如下.

定理2.2[6]若G是唯一k-可著色圖，則：

(1)G的每個(gè)同態(tài)像也是唯一可著色的；

(2)若對(duì)G添加一個(gè)新頂點(diǎn)w，使得w與G的除一個(gè)外的每個(gè)色類(lèi)中的至少一個(gè)頂點(diǎn)相鄰，則所得到的圖是唯一k-可著色的；

(3)若u是G中的一個(gè)度為k-1的頂點(diǎn)，則G-u也是唯一可著色的.

定理2.1是唯一可著色圖的一個(gè)簡(jiǎn)單但非常重要的結(jié)論.由定理2.1，容易得到下面的推論.

推論2.1設(shè)G是一個(gè)n-階唯一k-可著色圖，則G至少含有e*(G)條邊，其中，

由于(k-1)-樹(shù)是唯一k-可著色圖，且階數(shù)為n的(k-1)-樹(shù)恰含e*(G)條邊，因此推論2.1中的下界是可以取到的.一個(gè)圖G稱為k-樹(shù)，如果G要么是k+1個(gè)頂點(diǎn)的完全圖，要么在G中存在一個(gè)頂點(diǎn)u，使得u的鄰域是一個(gè)包含k個(gè)頂點(diǎn)的團(tuán)，且G-u仍是k-樹(shù).

1981年，Truszczyński[10]研究了恰含e*(G) 條邊的n-階唯一k-可著色圖的性質(zhì).另外，記r(k)為團(tuán)數(shù)是k-1的唯一k-可著色圖的最小的階數(shù)，Truszczyński證明了定理2.3.

定理2.3[10]r(3)=12，r(4)=10，且對(duì)任意的k≥5，r(k)=k+5.

2000年，Daneshgar等[11]通過(guò)引入唯一k-可著色圖的核的概念，推廣了 Truszczyński[10]得到的若干結(jié)果.唯一k-可著色圖G的核是指G中的一個(gè)導(dǎo)出子圖H，滿足H不含G的規(guī)模為1的色類(lèi)中的頂點(diǎn)，也不含G的度數(shù)為k-1的頂點(diǎn).Daneshgar等[11]證明了對(duì)任意的k≥3，不存在邊數(shù)極小的(k,2k)-核，但對(duì)任意的k≥4，存在邊數(shù)極小的(k,2k+1)-核，其中(k,n)-核是指n-階唯一k-可著色的核.

1990年，Xu[12]猜想如果G是一個(gè)階數(shù)為n，規(guī)模為e*(G)的唯一k-可著色圖，則G包含同構(gòu)于完全圖Kk的子圖.然而，在2001年，Akbari等[13]發(fā)現(xiàn)了一個(gè)階數(shù)為24的不含三角形的唯一3-可著色圖其邊數(shù)為45. 該結(jié)果否定了Xu[12]的猜想.更一般地，他們證明了對(duì)任意k≥3，存在邊數(shù)為e*(G)的不含Kk的唯一k-可著色圖.

1973年，Wang等[14]得到了不含三角形的唯一k-可著色圖頂點(diǎn)數(shù)的一個(gè)下界.

定理2.4[14]對(duì)任意k≥3，若唯一k-可著色圖G不含三角形，則G的頂點(diǎn)數(shù)嚴(yán)格大于k2+k-1.

1978年，Bollobás[15]得到了一個(gè)圖G是唯一k-可著色的兩個(gè)充分條件.

定理2.5[15]設(shè)G是一個(gè)n-階k-可著色圖，其中k≥2.

1983 年，Tucker[16]通過(guò)引入圖的順序著色，研究了完美圖的唯一可著色問(wèn)題.一個(gè)圖G稱為完美圖，如果對(duì)G的任意一個(gè)導(dǎo)出子圖H，有(H)=ω(H)成立，其中ω(H)是指H的團(tuán)數(shù)，即H的最大團(tuán)的頂點(diǎn)數(shù).Tucker[16]證明了對(duì)于兩類(lèi)完美圖G，G是順序k-可著色的當(dāng)且僅當(dāng)它是唯一k-可著色的.圖G稱為可比較圖，如果存在G的一個(gè)定向，使得其相鄰關(guān)系滿足傳遞性.圖G稱為弦圖，如果G的每個(gè)長(zhǎng)度大于等于4的圈均包含弦.

定理2.6[16]若G或G的補(bǔ)圖是可比較圖或弦圖，則G是順序k-可著色的當(dāng)且僅當(dāng)它是唯一k-可著色的.

另外，Tucker[16]提出如下猜想：

猜想2.1[16]設(shè)G是完美圖，則G是順序k-可著色的當(dāng)且僅當(dāng)它是唯一k-可著色的.

關(guān)于完美圖的唯一可著色的研究可參見(jiàn)文獻(xiàn)[17-18]，以及關(guān)于強(qiáng)完美圖猜想的綜述[19].

1998 年，Mahmoodian[20]引入了圖著色的定義集來(lái)研究唯一可著色圖.圖G著色的定義集是指G的一個(gè)帶有顏色的頂點(diǎn)子集S，滿足S的著色能唯一地?cái)U(kuò)展為G的一個(gè)(G)-著色.

1999年，Hajiabolhassan等[21]證明了如下定理：

定理2.7[21]圖G是唯一可著色的當(dāng)且僅當(dāng)G的任意著色c:V(G)→{1,2,…,(G)}的所有極小定義集恰包含(G)-1個(gè)頂點(diǎn).

2003 年，Daneshgar等[22]進(jìn)一步討論了與圖的唯一可著色和定義集相關(guān)的若干參數(shù).

2008 年，Hillar等[23]利用代數(shù)的方法刻畫(huà)了唯一可著色圖的性質(zhì)，并給出了判斷一個(gè)圖是否唯一可著色的算法，利用該算法，他們驗(yàn)證了Akbari等[13]給出的關(guān)于Xu[12]的猜想反例.

3 唯一可著色圖的存在性和構(gòu)造

關(guān)于圍長(zhǎng)較大的唯一k-可著色圖的研究主要分為存在性和構(gòu)造兩個(gè)方面.事實(shí)上，多數(shù)有關(guān)存在性的證明都采用的是構(gòu)造的方法.

1969年，Harary等[6]首先構(gòu)造了一個(gè)不含三角形的唯一3-可著色圖F(如圖1所示)，并通過(guò)F與完全圖Kk-3的聯(lián)運(yùn)算，得到如下結(jié)論：

定理3.1[6]對(duì)所有的k≥3，存在一個(gè)不含Kk的唯一k-可著色圖.

圖1 一個(gè)不含三角形的唯一3-可著色圖FFig.1 An uniquely 3-colorable graph F without triangles

注：在Harary等[6]的文章中，構(gòu)造的圖F存在錯(cuò)誤，沒(méi)有將邊v1v4,v2v3連接.

定理3.2[26]對(duì)任意的k≥1，存在不含三角形的唯一k-可著色圖.

1974年，Greenwell等[27]考慮了存在不含短奇圈的情況.

定理3.3[27]對(duì)任意的k≥3和給定的s，存在唯一k-可著色圖，其不含長(zhǎng)度小于等于s的奇圈.

1975年，Müller[28]解決了此問(wèn)題的一般情形(也見(jiàn)文獻(xiàn)[25])，即證明了定理3.4.

定理3.4[28]對(duì)任意的正整數(shù)k(≥3)和t，存在唯一k-可著色圖，其不含長(zhǎng)度小于等于t的圈.

其中Müller采用的也是構(gòu)造的方法.1976年，Bollobás等[29]給出了一種非構(gòu)造性的方法，即概率方法證明了此結(jié)論.

1998年，Emden-Weinert等[30]也利用概率方法，得到了一個(gè)帶有頂點(diǎn)數(shù)和最大度條件限制的結(jié)論.

定理3.5[30]對(duì)任意給定的正整數(shù)k和g，存在圍長(zhǎng)至少為g的唯一k-可著色圖，滿足其頂點(diǎn)數(shù)不超過(guò)k12(g+1)，最大度不超過(guò)5k13.

兩個(gè)圖G和H的弱積，記為G×H，其頂點(diǎn)集為V(G×H)=V(G)×V(H)，邊{(u,v),(u′,v′)} ∈E(G×H)當(dāng)且僅當(dāng)uu′∈E(G)且vv′∈E(H).

Greenwell等[27]在研究不含短奇圈的唯一k-可著色圖的存在性時(shí)，主要利用了唯一可著色圖與完全圖的弱積圖的唯一可著色性的關(guān)系.他們證明了若H是連通圖且(H)≥n+1，則H和完全圖Kn的弱積圖H×Kn是唯一n-可著色的.1985 年，Duffus等[31]進(jìn)一步研究了弱積圖的唯一可著色性質(zhì)，證明了若G和H都是包含Kk的唯一k-可著色圖，則G×H也是唯一k-可著色的.特別，對(duì)圖1所示的F以及任意4-色圖H，F(xiàn)×H是唯一3-可著色的.

1974 年，Osterweil[32]通過(guò)引入6-團(tuán)環(huán)構(gòu)造了一類(lèi)唯一3-可著色圖，并說(shuō)明可通過(guò)6-團(tuán)環(huán)構(gòu)造其它的唯一3-可著色圖類(lèi)以及唯一k-可著色圖類(lèi)，其中k≥3.

1996 年，Chia[33]結(jié)合圖的自同構(gòu)群方法，將Osterweil[32]給出的構(gòu)造唯一3-可著色圖的方法推廣到了唯一k-可著色圖上，其中k>3.

1974 年，Nieminen[34]構(gòu)造了一類(lèi)非唯一k-可著色圖G，滿足在G的任意k-著色下的q個(gè)色類(lèi)導(dǎo)出的子圖是唯一q-可著色的，其中q≤k-1，k≥3.

1993年，Chao等[35]通過(guò)構(gòu)造的方法證明了存在一類(lèi)不含三角形的唯一3-可著色的正則圖，這類(lèi)圖含有(24)2k個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)的度數(shù)均為k+5；從而得到如下定理:

定理3.6[35]對(duì)任意正整數(shù)k≥3，存在一類(lèi)不含Kk的唯一k-可著色正則圖.

進(jìn)一步，在1998年Chao等[36]也通過(guò)構(gòu)造的方法證明了定理3.7.

定理3.7[36]對(duì)任意的正整數(shù)n與r≥5，存在一類(lèi)含(26)n·2r-5個(gè)頂點(diǎn)的r-正則唯一3-可著色圖.

1997年，Daneshgar[37](也見(jiàn)文獻(xiàn)[38])引入了強(qiáng)迫技術(shù)來(lái)研究唯一可著色圖的構(gòu)造.對(duì)任意的正整數(shù)t和充分大的正整數(shù)k，Daneshgar利用強(qiáng)迫技術(shù)，構(gòu)造了團(tuán)數(shù)為k-t的唯一k-可著色圖，并分析了所構(gòu)造圖G的參數(shù)Λ(G)=|E(G)|-e*(G)的若干性質(zhì).

2007 年，Zhao等[39]利用遞歸的方法，構(gòu)造了一類(lèi)頂點(diǎn)數(shù)為n，邊數(shù)為e*(G)，且最小度為k的唯一k-可著色圖.

2016年，筆者等[40]給出了3種遞歸構(gòu)造唯一3-可著色圖的方法，可通過(guò)階數(shù)較小的唯一3-可著色圖構(gòu)造階數(shù)較大的唯一3-可著色圖.并且，給出了Xu[12]猜想的一個(gè)簡(jiǎn)單反例G16，如圖2所示.此圖是不含三角形的唯一3-可著色圖，其頂點(diǎn)數(shù)為16，邊數(shù)為29.

圖2 唯一3-可著色圖 G16Fig.2 An uniquely 3-colorable graph G16

在圖G16的基礎(chǔ)上，筆者構(gòu)造了一類(lèi)4-正則且不含三角形的唯一3-可著色圖.結(jié)合定理3.7可得到定理3.8：

定理3.8[40]對(duì)任意正整數(shù)r≥4，存在一類(lèi)r-正則唯一3-可著色圖.

4 唯一可著色平面圖

1969年，Chartrand等[7]開(kāi)始對(duì)平面圖的唯一可著色問(wèn)題展開(kāi)研究.唯一1-可著色平面圖是平凡的，即只有K1. 容易證明，唯一2-可著色平面圖只有連通的平面二部圖.對(duì)于更一般的情況，他們證明了定理4.1.

定理4.1[7](1)至少含4個(gè)頂點(diǎn)的唯一3-可著色平面圖至少包含2個(gè)三角形；

(2)唯一4-可著色平面圖是極大平面圖；

(3)不存在唯一5-可著色的平面圖.

特別，設(shè)G是一個(gè)色數(shù)為3的平面圖.如果G包含三角形T，使得對(duì)G中任意頂點(diǎn)v有一個(gè)三角形序列T,T1,T2,…,Tm，序列中相繼的三角形有一條公共邊，而v在Tm中，則G是唯一3-可著色的.

對(duì)唯一4-可著色平面圖，有下面的猜想：

猜想4.1[41]若極大平面圖G是唯一4-可著色的，則G是遞歸極大平面圖.其中G稱為遞歸極大平面圖，如果G可在K4的基礎(chǔ)上通過(guò)不斷地在某個(gè)3-度面上嵌入3-度頂點(diǎn)得到.

猜想4.1也被稱為唯一4-可著色平面圖猜想，該猜想最初是以邊著色的形式提出的.因?yàn)橐粋€(gè)給定的平面圖與其對(duì)偶圖是相互對(duì)應(yīng)的，故平面圖的點(diǎn)著色、面著色以及邊著色在一定條件下可以相互轉(zhuǎn)化.

1973 年，Greenwell等[42]首先研究了圖的唯一邊著色問(wèn)題.Fiorini等[43]，及Fisk[44]于1977年分別提出了下述猜想：

猜想4.2[43-44]每個(gè)至少有4個(gè)頂點(diǎn)的唯一3-邊可著色立方平面圖包含三角形.

根據(jù)一個(gè)平面圖與其對(duì)偶圖的結(jié)構(gòu)特征，易證明猜想4.1與猜想4.2是等價(jià)的.1988年， Hind[45]證明了猜想4.2的極小反例不含長(zhǎng)為4的圈.1996年，Goldwasser等[46]證明了猜想4.2的極小反例是循環(huán)5-邊連通的.1998年，F(xiàn)owler[47]在其博士論文中利用類(lèi)似于證明四色定理的方法給出了猜想4.1的一個(gè)證明，但該證明未見(jiàn)正式發(fā)表.

1977年，Aksionov[48]改進(jìn)了唯一3-可著色平面圖中三角形數(shù)的下界，并且，詳細(xì)刻畫(huà)了恰含3個(gè)三角形的唯一3-可著色平面圖的結(jié)構(gòu)特征.

定理4.2[48]階數(shù)大于等于6的唯一3-可著色平面圖G至少包含3個(gè)三角形.并且，若G恰含3個(gè)三角形，則：

(1)G中的3個(gè)三角形依次相鄰；

(2)G的所有面部圈中除3個(gè)3-圈，1個(gè)5-圈以外，其余面部圈均為4-圈；

(3)G的面部5-圈的邊界上存在一個(gè)2-度頂點(diǎn).

2017年，筆者等[49]對(duì)恰含4個(gè)三角形的唯一3-可著色平面圖的結(jié)構(gòu)特征進(jìn)行了刻畫(huà)，得到以下定理4.3.

定理4.3[49]若階數(shù)大于等于6的唯一3-可著色平面圖G恰含4個(gè)三角形，則 0≤|E(G)|-2|V(G)|+3≤1，且：

(1)當(dāng)|E(G)|-2|V(G)|+3=1時(shí)，對(duì)任意的i≥5，G中不存在i-度面；

(2)當(dāng)|E(G)|-2|V(G)|+3=0時(shí)，F(xiàn)5+(G) 中只包含兩個(gè)5-度面或一個(gè)6-度面，其中F5+(G) 表示G中所有度數(shù)大于等于5的面構(gòu)成的集合.

設(shè)G是一個(gè)唯一k-可著色圖，如果對(duì)任意的邊e∈E(G)，都有G-e不是唯一k-可著色的，則G稱為邊臨界的.記size(n)為n個(gè)頂點(diǎn)的邊臨界唯一3-可著色平面圖的邊數(shù)的最小上界.

Aksionov 在文獻(xiàn)[48]中猜想：size(n)= 2n-3且每個(gè)唯一3-可著色平面圖包含相鄰三角形.

然而，在同一年，Mel’nikov等[50]構(gòu)造了一個(gè)反例G(如圖3所示)，圖G包含16個(gè)頂點(diǎn)和30條邊且不含相鄰三角形，從而否定了 Aksionov 提出的猜想.

圖3 Mel’nikov等猜想的反例及其3-著色

Fig.3 A counterexample of the Mel’nikov and Steinberg’s conjecture and its 3-coloring

對(duì)唯一3-可著色平面圖中是否存在相鄰三角形的問(wèn)題，筆者等[49]給出了下面的結(jié)論：

定理4.4[49]若唯一3-可著色平面圖G中的三角形數(shù)不超過(guò)4，則G包含相鄰三角形.

并且，對(duì)任意大于等于5的整數(shù)k，構(gòu)造了唯一3-可著色平面圖G，滿足G包含k個(gè)三角形，但不含相鄰三角形 (如圖4 所示).

此外，Mel’nikov等證明了圖3所示的平面圖G是邊臨界的.將G復(fù)制多次，并將其粘連起來(lái)，也就是說(shuō)，使得這些圖依次有一條公共邊，這樣可得到一類(lèi)邊臨界唯一3-可著色平面圖.基于此，Mel’nikov等提出了下面的問(wèn)題：

圖4 不含相鄰三角形的唯一3-可著色平面圖構(gòu)造

Fig.4 Construction of uniquely 3-colorable planar graphs without adjacent triangles

問(wèn)題4.2[50]是否存在整數(shù)n0，使得若一個(gè)平面圖G中的任意兩個(gè)三角形的距離大于等于n0，則G不是唯一3-可著色的? 有可能n0=1.

圖5 Matsumoto 構(gòu)造的邊臨界唯一3-可著色平面圖

Fig.5 The edge-critical uniquely 3-colorable planar graph constructed by Matsumoto

另外，Matsumoto 引入了Δ-面圈的概念.對(duì)一個(gè)平面圖G，G中的一個(gè)Δ-面圈C=T1T2…Tk是指G的由k個(gè)三角形Ti的頂點(diǎn)和邊構(gòu)成的子圖，其中Ti與Ti+1有一條公共邊，i=1,2,…,k，且Tk+1=T1. 例如，圖6所示的圖是一個(gè)Δ-面圈.

圖6 一個(gè)Δ-面圈Fig.6 A Δ-face cycle

通過(guò)證明邊臨界唯一3-可著色平面圖不含Δ-面圈，Matsumoto 得到定理4.5.

筆者通過(guò)分析唯一3-可著色平面圖中Tri-子圖的性質(zhì)，改進(jìn)了Matsumoto 得到的關(guān)于size(n)的上界.設(shè)G是唯一3-可著色平面圖，H是由三角形序列T1,T2,…,Tt構(gòu)成的G的子圖，且對(duì)每個(gè)Tj，存在i∈{1,2,…,j-1}使得Tj與Ti有公共邊，其中j=2,3,…,t，則稱H為G的Tri-子圖.G的一個(gè)Tri-子圖稱為極大的，如果G中不存在Tri-子圖H′，使得H?H′.

定理4.6[52]設(shè)G是一個(gè)唯一3-可著色平面圖且G不含分離3-圈，G0是G的一個(gè)唯一3-可著色子圖，且H1,H2分別是G的兩個(gè)極Tri-子圖.若E(G0)∩E(Hi)=?, 其中i=1,2, 則有

(1)G0和Hi至多有一個(gè)公共頂點(diǎn)，其中i=1,2；

(2)對(duì)任意的i∈{1,2}，有e(V(G0),V(Hi))≤3，特別，若G0和Hi有一個(gè)公共頂點(diǎn)v, 則e(V(G0-v),V(Hi-v))≤1；

(3)若H1與H2有一個(gè)公共頂點(diǎn)v,G0與Hi有一個(gè)公共頂點(diǎn)vi且v≠vi, 其中i=1,2, 則G0,H1與H2的并是唯一3-可著色的.

進(jìn)一步，引入并分析了唯一3-可著色平面圖的Tri-特征圖的結(jié)構(gòu)特征(詳細(xì)定義參見(jiàn)文獻(xiàn)[52])，在此基礎(chǔ)上證明了定理4.7.

另外，筆者證明了定理4.8.

定理4.8[53]任意唯一3-可著色平面圖包含一個(gè)3-度面與一個(gè)k-度面相鄰，其中3≤k≤5；進(jìn)一步，采用構(gòu)造的方法，證明了存在唯一3-可著色平面圖，其中每個(gè)3-度面既不與i-度面相鄰，也不與j-度面相鄰，其中i,j∈{3,4,5} 且i≠j.

同時(shí)，提出如下猜想：

猜想4.3[53]設(shè)G是3-連通唯一3-可著色平面圖，則G中存在3-度面與k-度面相鄰，其中3≤k≤4.

圖7 不包含相鄰3-度面與3-度面、相鄰3-度面與5-度面的唯一3-可著色平面圖

Fig.7 An uniquely 3-colorable planar graph with neither adjacent 3-face and 3-face nor adjacent 3-face and 5-face

推論4.1[53]任意滿足n≥11和n≡2(mod 3)的奇數(shù)n，有

猜想4.5設(shè)G是一個(gè)唯一3-可著色平面圖，則G中存在兩個(gè)含有公共頂點(diǎn)的三角形.

5 結(jié)論與相關(guān)研究

本文對(duì)唯一可著色圖，特別是唯一3-可著色平面圖的相關(guān)研究結(jié)果進(jìn)行了綜述，主要從結(jié)構(gòu)性質(zhì)、存在性、構(gòu)造等方面對(duì)其展開(kāi)介紹，并總結(jié)了一些目前尚未解決的問(wèn)題.

類(lèi)似于唯一可著色圖，唯一邊可著色圖和唯一全可著色圖的問(wèn)題也被相繼提出并進(jìn)行研究.

圖G的一個(gè)k-邊著色是指從E到顏色集 {1,2,…,k}的映射f，滿足對(duì)任意的xy∈E，有f(x)≠f(y).圖G的邊色數(shù)，記作′(G)，是指使得G有k-邊著色的最小正整數(shù)k.圖G稱為唯一邊可著色的，如果E可以被唯一地劃分為′(G)個(gè)色類(lèi).關(guān)于唯一邊可著色圖，有下面重要結(jié)論：

定理5.1[54]對(duì)任意k≥4，唯一k-邊可著色圖只有星K1,k.

定理5.1最初是Wilson 于 1967年提出的猜想，被Thomason 于 1978年給出了證明.當(dāng)k=1或k=2時(shí)，判斷唯一k-邊可著色圖的問(wèn)題是平凡的.當(dāng)k=3時(shí)，有許多相關(guān)研究結(jié)果和未解決的問(wèn)題[42,54-57].

猜想5.1[55]設(shè)G是一個(gè)唯一3-邊可著色簡(jiǎn)單立方圖，則G包含Petersen-子式或三角形.

猜想5.2[56]設(shè)G是一個(gè)唯一3-邊可著色簡(jiǎn)單立方圖，則G包含snark-子式或三角形.

圖G的一個(gè)k-全著色[58]是指從V∪E到顏色集{1,2,…,k}的映射f，滿足對(duì)任意的相鄰或關(guān)聯(lián)元素x,y∈V∪E，有f(x)≠f(y)，其中頂點(diǎn)u與邊e關(guān)聯(lián)是指u是e的一個(gè)端點(diǎn).圖G的全色數(shù)，記作″(G)，是指使得G有k-全著色的最小正整數(shù)k.圖G稱為唯一全可著色的，如果V∪E可以被唯一地劃分為″(G)個(gè)色類(lèi).例如，路和長(zhǎng)為n(n≡0mod3)的圈是唯一全可著色圖.1995年，Mahmoodian等[59]提出了如下猜想：

猜想5.3[59]除空?qǐng)D、路和長(zhǎng)為n(n≡0mod3)的圈之外，再?zèng)]有唯一全可著色圖.

1997年和2003年，Akbari 等[60-61]得到了唯一全可著色圖的若干性質(zhì)，并證明了一些圖類(lèi)不是唯一全可著色的，部分肯定了猜想5.3.