圖在約束條件下的鄰點(diǎn)可區(qū)別全染色

崔福祥, 楊 超, 葉宏波

(上海工程技術(shù)大學(xué) 數(shù)理與統(tǒng)計(jì)學(xué)院, 上海 201620)

0 引 言

圖染色理論在物理、化學(xué)、計(jì)算機(jī)科學(xué)、網(wǎng)絡(luò)理論、社會(huì)科學(xué)等領(lǐng)域有著廣泛的應(yīng)用, 具體涉及安排問(wèn)題、時(shí)間表問(wèn)題和計(jì)算機(jī)寄存器分配問(wèn)題等. 圖的可區(qū)別染色問(wèn)題來(lái)源于頻率分配問(wèn)題, 該問(wèn)題產(chǎn)生于移動(dòng)通訊的迅速發(fā)展, 客戶急劇增加, 導(dǎo)致用戶數(shù)量不斷增長(zhǎng)與通訊網(wǎng)絡(luò)資源有限擴(kuò)容二者之間的矛盾日益突出,在此背景驅(qū)動(dòng)下, 圖的可區(qū)別染色問(wèn)題已成為當(dāng)前國(guó)內(nèi)外學(xué)者研究的熱點(diǎn).Vizing[1]和 Behzad[2]分別于1964和1965年獨(dú)立地給出了全染色的定義，并提出了點(diǎn)可區(qū)別全染色猜想: 任意圖的點(diǎn)可區(qū)別全色數(shù)不超過(guò)Δ+2.隨著研究的不斷深化, Zhang等[3]對(duì)點(diǎn)可區(qū)別全染色進(jìn)行弱化, 定義了圖的鄰點(diǎn)可區(qū)別全染色概念, 同時(shí)給出了鄰點(diǎn)可區(qū)別全染色猜想: 任意圖的鄰點(diǎn)可區(qū)別全色數(shù)不超過(guò)Δ+3.目前，這兩個(gè)猜想均未被解決,也沒(méi)有發(fā)現(xiàn)這些猜想的反例. 為了更深入地研究圖的可區(qū)別染色問(wèn)題, 本文提出了(3)-鄰點(diǎn)可區(qū)別全染色((3)-AVDTC) 概念,這個(gè)概念極大豐富了文獻(xiàn)[1-6] 中的研究?jī)?nèi)容, 考慮的問(wèn)題較以前更為全面, 為圖染色在其他領(lǐng)域中的應(yīng)用奠定了理論基礎(chǔ). 在介紹主要工作之前, 先介紹與本文相關(guān)的一些概念.

文中論及的圖均為無(wú)向簡(jiǎn)單圖, 且沒(méi)有定義的術(shù)語(yǔ)和符號(hào)均采用于文獻(xiàn)[7].符號(hào)[s,t] 表示非負(fù)整數(shù)集{s,s+1,s+2,…,t}, 其中,s和t均為整數(shù), 且滿足0≤s

定義1設(shè)f:V(G)∪E(G)→{1,2,…,k} 是圖G的一個(gè)正常k-全染色.對(duì)任意的邊xy∈E(G), 如果有C[f;x]≠C[f;y] 成立, 則稱(chēng)f是圖G的一個(gè)k-(3)-鄰點(diǎn)可區(qū)別全染色(簡(jiǎn)記為 (3)-AVDTC). 圖G的(3)-鄰點(diǎn)可區(qū)別全染色中所需最少的顏色數(shù)叫做G的(3)-鄰點(diǎn)可區(qū)別全色數(shù), 記為″(3)as(G).

本文將對(duì)一類(lèi)特殊極大平面圖的(3)-鄰點(diǎn)可區(qū)別全染色問(wèn)題進(jìn)行研究. 極大平面圖是指每個(gè)面的邊界均為三角形, 也稱(chēng)為三角剖分圖. 由于著名的四色定理、唯一4-可著色平面圖猜想等的研究對(duì)象均與極大平面圖有關(guān)聯(lián), 所以極大平面圖一直都是專(zhuān)家學(xué)者們研究的重點(diǎn)對(duì)象, 他們從諸如度序列、構(gòu)造、著色、可遍歷性和生成運(yùn)算等多方面對(duì)極大平面圖相關(guān)問(wèn)題展開(kāi)了研究[8-9].

定義2[10]從平面圖K4出發(fā), 逐次實(shí)施擴(kuò)3-輪運(yùn)算而得到的極大平面圖稱(chēng)為遞歸極大平面圖. 一個(gè)遞歸極大平面圖G稱(chēng)為(2,2)-遞歸極大平面圖, 如果G中恰好有2 個(gè)度數(shù)為3 的頂點(diǎn), 并且這兩個(gè)3 度頂點(diǎn)之間的距離為2. 進(jìn)一步, 如果圖G有2 個(gè)3 度頂點(diǎn)所在長(zhǎng)度為2 路中的3 個(gè)頂點(diǎn)存在一個(gè)公共的相鄰頂點(diǎn), 則稱(chēng)圖G為相鄰型, 否則稱(chēng)為非相鄰型.

容易證明5-階(2,2)-遞歸極大平面圖只有1 個(gè), 如圖 1 所示,6-階(2,2)-遞歸極大平面圖也只有1 個(gè), 如圖 2 所示.

圖1 5-階(2,2)-遞歸極大平面圖Fig.1 (2,2)-recursive maximal planar graph on 5 vertices

圖2 6-階(2,2)-遞歸極大平面圖Fig.2 (2,2)-recursive maximal planar graph on 6 vertices

1 主要結(jié)果及證明

引理1[10]設(shè)G是一個(gè)n階遞歸極大平面圖, 則G至少含有2 個(gè)3 度頂點(diǎn), 并且當(dāng)n≥5時(shí), 任意兩個(gè)3 度頂點(diǎn)之間均不相鄰.

引理2[10](1)不存在恰有2個(gè)相鄰的3度頂點(diǎn)的極大平面圖;

(2)不存在恰有3個(gè)兩兩相鄰的3度頂點(diǎn)的極大平面圖.

引理3[10](1)設(shè)G是一個(gè)階數(shù)大于等于6 的(2,2)-遞歸極大平面圖, 則對(duì)G中每個(gè)3 度頂點(diǎn)v,其鄰域N(v) 中恰有一個(gè)頂點(diǎn)的度數(shù)為4;

(2)每個(gè)不相鄰型n(≥5)-階(2,2)-遞歸極大平面圖G有且只有一個(gè)度數(shù)為n-1 的頂點(diǎn), 稱(chēng)此頂點(diǎn)為圖G的中心頂點(diǎn).

定理1設(shè)G是一個(gè)簡(jiǎn)單圖且G中存在相鄰的Δ-頂點(diǎn),則″(3)as(G)≥Δ(G)+2.

證明反證法. 假設(shè)″(3)as(G)≤Δ(G)+1. 因?yàn)椤?3)as(G)≥Δ(G)+1,所以″(3)as(G)=Δ(G)+1. 設(shè)uv∈E(G) 且dG(u)=dG(v)=Δ(G), 用Δ(G)+1種顏色無(wú)論怎么染色必有C2[f,u]=C2[f,v], 得矛盾.因此,″(3)as(G)≥Δ(G)+2.

將圖G中的每個(gè)頂點(diǎn)與圖H中的每個(gè)頂點(diǎn)之間用邊連接, 得到的新圖稱(chēng)為圖G與圖H的聯(lián)圖, 記為GH.下面給出聯(lián)圖P2Pn的(3)-鄰點(diǎn)可區(qū)別全色數(shù).

定理2″(3)as(P2Pn)=Δ(P2Pn)+2.

證明設(shè)兩條路P2=uv,Pn=x1x2…xn. 令H=P2Pn. 由聯(lián)圖的定義知,dH(u)=dH(v)=Δ(H),dH(x1)=dH(xn)=3,dH(xi)=4,i∈[2,n-1].由定理1 知,″(3)as(H)≥Δ(H)+2. 為證″(3)as(H)=Δ(H)+2, 下面僅需證″(3)as(H)≤Δ(H)+2. 為此只需給出H的一個(gè)(Δ+2)-(3)-AVDTC 即可. 定義H的一個(gè)全染色f如下:f(u)=1,f(v)=2,f(x1)=n+1,f(x2)=n,f(xi)=i,i∈[3,n],f(uv)=n+3,f(uxi)=i+1,i∈[1,n],f(vx1)=n+2,f(vx2)=n+1,f(vxi)=n+3-f(xi),i∈[3,n],f(x1x2)=n-1,f(xixi+1)=i-1,i∈[2,n-1].

因?yàn)閐H(u)=dH(v)=Δ(H),dH(x1)=dH(xn)=3,dH(xi)=4,i∈[2,n-1],所以C(f,u)≠C(f,xi),C[f,u]≠C[f,xi],C2[f,u]≠C2[f,xi],i∈[1,n];C(f,v)≠C(f,xi),C[f,v]≠C[f,xi],C2[f,v]≠C2[f,xi],i∈[1,n];C(f,x1)≠C(f,x2),C[f,x1]≠C[f,x2];C(f,xn-1)≠C(f,xn),C[f,xn-1]≠C[f,xn].對(duì)如此構(gòu)造的全染色f, 因?yàn)閚+2∈{C(f,u),C[f,u],C2[f,u]},n+2{C(f,v),C[f,v],C2[f,v]}, 所以C(f,u)≠C(f,v),C[f,u]≠C[f,v],C2[f,u]≠C2[f,v].

因?yàn)镃(f,x1)={2,n-1,n+2},C(f,x2)={1,3,n-1,n+1},C(f,xi)={i-2,i-1,i+1,n-i-3},i∈[3,n-1],C(f,xn)={3,n-2,n+1};C[f,x1]={2,n-1,n+1,n+2},C[f,x2]={1,3,n-1,n,n+1},C[f,xi]={i-2,i-1,i,i+1,n-i-3},i∈[3,n-1],C[f,xn]={3,n-2,n,n+1};C2[f,x1]={1,2,n-1,n,n+1,n+2},C2[f,xi]=C[f,xi]∪{1,2},i∈[2,n].所以C2[f,x1]≠C2[f,x2],C(f,xi)≠C(f,xi+1),C[f,xi]≠C[f,xi+1],C2[f,xi]≠C2[f,xi+1],i∈[2,n-2],C2[f,xn-1]≠C2[f,xn].

綜上, 全染色f是H的一個(gè)(n+3)-(3)-AVDTC. 因此,有″(3)as(H)=n+3=Δ(H)+2.

定理3若G是一個(gè)n-階(2,2)-遞歸極大平面圖, 則″(3)as(G)=Δ(G)+3.

證明數(shù)學(xué)歸納法. 當(dāng)n=5, 6 時(shí), 它們的一個(gè)(Δ+3)-(3)-AVDTC 分別如圖1 和圖2 所示.下面考慮n-階(2,2)-遞歸極大平面圖在n≥7 時(shí)的(3)-AVDTC.

情形1G是相鄰型的, 如圖3所示.

圖3 相鄰型的圖GFig.3 Graph G with an adjacent type

設(shè)P2=uv,Pn=x1x2…xn. 圖G=V(G)∪E(G),V(G)=V(P2Pn)∪{t},E(G)=E(P2Pn)∪{tx1,tu,tv}. 由定理2 知″(3)as(P2Pn)=Δ(P2Pn)+2. 當(dāng)n=5,6 時(shí),″(3)as(G)=Δ(G)+3. 當(dāng)n≥7 時(shí),″(3)as(G)≥Δ(G)+3. 下面僅需給出G的一個(gè)(Δ+3)-(3)-AVDTC 即可.P2Pn的頂點(diǎn)和邊保持定理2 中的染色f不變.設(shè)f*為G的一個(gè)全染色, 定義f*的一個(gè)全染色如下:f*(tx1)=Δ+2,f*(tu)=Δ+3,f*(tv)=1,f*(u)∈[1,Δ+2]{f(x1),f(u),f(v),1,Δ+2},f*(m)=f(m),m∈V(P2Pn)∪E(P2Pn). 下面分析相鄰頂點(diǎn)色集合之間的關(guān)系.

因?yàn)棣?3∈{C(f*,t),C[f*,t],C2[f*,t]},Δ+3{C(f*,x1),C[f*,x1],C2[f*,x1],C(f*,v),C[f*,v],C2[f*,v]}, 所以C(f*,t)≠C(f*,x1),C[f*,t]≠C[f*,x1],C2[f*,t]≠C2[f*,x1],C(f*,t)≠C(f*,v),C[f*,t]≠C[f*,v],C2[f*,t]≠C2[f*,v]. 因?yàn)閐G(t)=3,dG(u)=Δ(G), 所以C(f*,t)≠C(f*,u),C[f*,t]≠C[f*,u],C2[f*,t]≠C2[f*,u]. 設(shè)pq∈V(P2Pn),則有C(f*,p)≠C(f*,q),C[f*,p]≠C[f*,q],C2[f*,p]≠C2[f*,q]. 綜上,f*是圖G的一個(gè)(Δ+3)-(3)-AVDTC. 故″(3)as(G)=Δ(G)+3.

情形2G是非相鄰型的.

假設(shè)對(duì)n-階(2,2)-遞歸極大平面圖G有″(3)as(G)=Δ(G)+3 成立.設(shè)f是圖G的一個(gè)(Δ+3)-(3)-AVDTC. 考察頂點(diǎn)數(shù)為n+1 的情況,設(shè)G*是一個(gè)n+1-階(2,2)-遞歸極大平面圖,G*=G+u,dG*(u)=3,N(u)={x,y.z},g∈N(z). 不妨設(shè)x為中心頂點(diǎn), 由引理3, 不失一般性,設(shè)dG(z)=3. 下面分兩種情況對(duì)圖G的結(jié)構(gòu)進(jìn)行討論.

情形2.1dG(x)=n-1,dG(y)≥5,dG(z)=3,dG(g)=4， 如圖4(a)所示.

對(duì)于圖G*,dG*(x)=n,dG*(y)≥6,dG*(z)=4,dG*(g)=4,dG*(u)=3. 設(shè)是圖G*的一個(gè)全染色, 定義如下:(uz)∈[1,Δ+3]C2[f,g]∪{f(xz),f(yz)},(uy)∈C2[f,y]C[f,y]∪{(uz)},(ux)∈C2[f,x]C[f,x]∪{(uy),(uz)},(u)∈C2[f,y]{(ux),(uy),(uz),f(x),f(y),f(z)},(t)=f(t),t∈V(G*)∪E(G*){ux,uy,uz,u}.因?yàn)閐G*(u)

情形2.2dG(x)=n-1,dG(y)=4,dG(z)=3,dG(g)≥5, 如圖4(b)所示.

圖4 情形2.1和情形2.2 的結(jié)構(gòu)示意圖Fig.4 Structure of Case 2.1 and Case 2.2

對(duì)于圖G*,dG*(x)=n,dG*(y)=5,dG*(z)=4,dG*(g)≥5,dG*(u)=3. 設(shè)ρ是圖G*的一個(gè)全染色, 定義ρ如下:ρ(uz)∈[1,Δ+3]C2[f,g]∪{f(xz),f(yz)},ρ(uy)∈C2[f,y]C[f,y]∪{ρ(uz)},ρ(ux)∈[1,Δ+3]C[f,x]∪C2[f,y]∪{ρ(uy),ρ(uz)},ρ(u)∈C2[f,y]{ρ(ux),ρ(uy),ρ(uz),f(x),f(y),f(z)},ρ(t)=f(t),t∈V(G*)∪E(G*){ux,uy,uz,u}.因?yàn)閐G*(u)

基于情形1和2, 本定理得證.

□

2 討 論

極大平面圖由于其特殊的結(jié)構(gòu)使得它在數(shù)學(xué)和計(jì)算機(jī)科學(xué)領(lǐng)域被廣泛研究, 尤其在四色定理的研究中發(fā)揮著極其重要的作用.本文僅對(duì)一類(lèi)極大平面圖的(3)-鄰點(diǎn)可區(qū)別全染色進(jìn)行了研究, 希望感興趣的讀者在更多極大平面圖的(3)-鄰點(diǎn)可區(qū)別全染色問(wèn)題上貢獻(xiàn)力量. 圖的(3)-鄰點(diǎn)可區(qū)別全染色是鄰點(diǎn)可區(qū)別全染色的一個(gè)推廣, 受Zhang等在文獻(xiàn)[3]的鄰點(diǎn)可區(qū)別全染色猜想的啟發(fā), 本文進(jìn)一步提出圖的(3)-鄰點(diǎn)可區(qū)別全染色猜想:

猜想若圖G是一個(gè)簡(jiǎn)單圖, 則″(3)as(G)≤Δ(G)+3.