唯一可著色圖研究進展

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

1 引言及預備知識

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

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

此外，唯一可著色圖可根據其色多項式來定義.設P(G,x)為圖G的色多項式，則G是唯一k-可著色圖當且僅當P(G,k)=k!，關于圖的色多項式的研究可參見文獻[1-3].

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

圖的唯一可著色問題與經典的圖著色問題研究的側重點有所不同.經典的圖著色問題主要在刻畫給定圖的色數，而唯一可著色問題主要判斷哪些圖是唯一可著色的.

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

本文主要介紹唯一可著色圖研究的重要結論，特別是唯一3-可著色平面圖的相關結果.文中未給出的定義及符號，請參照文獻[9].

2 唯一可著色圖的性質

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

定理2.1[4]若G是一個唯一k-可著色圖，則在G的每個k-著色下，G中任意兩個色類導出的子圖是連通的.

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

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

(1)G的每個同態像也是唯一可著色的；

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

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

定理2.1是唯一可著色圖的一個簡單但非常重要的結論.由定理2.1，容易得到下面的推論.

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

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

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

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

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

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

1973年，Wang等[14]得到了不含三角形的唯一k-可著色圖頂點數的一個下界.

定理2.4[14]對任意k≥3，若唯一k-可著色圖G不含三角形，則G的頂點數嚴格大于k2+k-1.

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

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

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

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

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

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

關于完美圖的唯一可著色的研究可參見文獻[17-18]，以及關于強完美圖猜想的綜述[19].

1998 年，Mahmoodian[20]引入了圖著色的定義集來研究唯一可著色圖.圖G著色的定義集是指G的一個帶有顏色的頂點子集S，滿足S的著色能唯一地擴展為G的一個(G)-著色.

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

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

2003 年，Daneshgar等[22]進一步討論了與圖的唯一可著色和定義集相關的若干參數.

2008 年，Hillar等[23]利用代數的方法刻畫了唯一可著色圖的性質，并給出了判斷一個圖是否唯一可著色的算法，利用該算法，他們驗證了Akbari等[13]給出的關于Xu[12]的猜想反例.

3 唯一可著色圖的存在性和構造

關于圍長較大的唯一k-可著色圖的研究主要分為存在性和構造兩個方面.事實上，多數有關存在性的證明都采用的是構造的方法.

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

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

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

注：在Harary等[6]的文章中，構造的圖F存在錯誤，沒有將邊v1v4,v2v3連接.

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

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

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

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

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

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

1998年，Emden-Weinert等[30]也利用概率方法，得到了一個帶有頂點數和最大度條件限制的結論.

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

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

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

1974 年，Osterweil[32]通過引入6-團環構造了一類唯一3-可著色圖，并說明可通過6-團環構造其它的唯一3-可著色圖類以及唯一k-可著色圖類，其中k≥3.

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

1974 年，Nieminen[34]構造了一類非唯一k-可著色圖G，滿足在G的任意k-著色下的q個色類導出的子圖是唯一q-可著色的，其中q≤k-1，k≥3.

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

定理3.6[35]對任意正整數k≥3，存在一類不含Kk的唯一k-可著色正則圖.

進一步，在1998年Chao等[36]也通過構造的方法證明了定理3.7.

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

1997年，Daneshgar[37](也見文獻[38])引入了強迫技術來研究唯一可著色圖的構造.對任意的正整數t和充分大的正整數k，Daneshgar利用強迫技術，構造了團數為k-t的唯一k-可著色圖，并分析了所構造圖G的參數Λ(G)=|E(G)|-e*(G)的若干性質.

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

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

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

在圖G16的基礎上，筆者構造了一類4-正則且不含三角形的唯一3-可著色圖.結合定理3.7可得到定理3.8：

定理3.8[40]對任意正整數r≥4，存在一類r-正則唯一3-可著色圖.

4 唯一可著色平面圖

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

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

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

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

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

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

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

猜想4.1也被稱為唯一4-可著色平面圖猜想，該猜想最初是以邊著色的形式提出的.因為一個給定的平面圖與其對偶圖是相互對應的，故平面圖的點著色、面著色以及邊著色在一定條件下可以相互轉化.

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

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

根據一個平面圖與其對偶圖的結構特征，易證明猜想4.1與猜想4.2是等價的.1988年， Hind[45]證明了猜想4.2的極小反例不含長為4的圈.1996年，Goldwasser等[46]證明了猜想4.2的極小反例是循環5-邊連通的.1998年，Fowler[47]在其博士論文中利用類似于證明四色定理的方法給出了猜想4.1的一個證明，但該證明未見正式發表.

1977年，Aksionov[48]改進了唯一3-可著色平面圖中三角形數的下界，并且，詳細刻畫了恰含3個三角形的唯一3-可著色平面圖的結構特征.

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

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

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

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

2017年，筆者等[49]對恰含4個三角形的唯一3-可著色平面圖的結構特征進行了刻畫，得到以下定理4.3.

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

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

(2)當|E(G)|-2|V(G)|+3=0時，F5+(G) 中只包含兩個5-度面或一個6-度面，其中F5+(G) 表示G中所有度數大于等于5的面構成的集合.

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

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

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

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

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

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

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

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

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

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

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

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

圖5 Matsumoto 構造的邊臨界唯一3-可著色平面圖

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

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

圖6 一個Δ-面圈Fig.6 A Δ-face cycle

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

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

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

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

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

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

進一步，引入并分析了唯一3-可著色平面圖的Tri-特征圖的結構特征(詳細定義參見文獻[52])，在此基礎上證明了定理4.7.

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

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

同時，提出如下猜想：

猜想4.3[53]設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)的奇數n，有

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

5 結論與相關研究

本文對唯一可著色圖，特別是唯一3-可著色平面圖的相關研究結果進行了綜述，主要從結構性質、存在性、構造等方面對其展開介紹，并總結了一些目前尚未解決的問題.

類似于唯一可著色圖，唯一邊可著色圖和唯一全可著色圖的問題也被相繼提出并進行研究.

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

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

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

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

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

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

猜想5.3[59]除空圖、路和長為n(n≡0mod3)的圈之外，再沒有唯一全可著色圖.

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