平面圖的動態(tài)染色

卜月華, 楊瑞盈

(1.浙江師范大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院,浙江 金華 321004;2.浙江師范大學(xué) 行知學(xué)院,浙江 蘭溪 321100)

0 引 言

本文考慮有限簡單圖.對于一個圖G,把它的頂點(diǎn)集、邊集、面集、頂點(diǎn)v的度、頂點(diǎn)v的鄰點(diǎn)集及圍長分別記作V(G),E(G),F(G),dG(v),NG(v)及g(G),在不引起混淆的情況下,dG(v),NG(v)可分別簡記為d(v),N(v);對于平面圖G的一個面f,用b(f)表示面f的周界,d(f)表示b(f)的邊數(shù).若d(f)=k(d(f)≥k,d(f)≤k),則稱f為一個k-面(k+-面,k--面);對于平面圖G的一個頂點(diǎn)v,若d(v)=k(d(v)≥k,d(v)≤k),則稱v為一個k-點(diǎn)(k+-點(diǎn),k--點(diǎn)).對于2個正整數(shù)k,r,圖G的(k,r)-動態(tài)染色(簡稱(k,r)-染色)是指映射φ:V(G)→{1,2,…,k},滿足:

1)對任意的uv∈E(G),有φ(u)≠φ(v);

2)對任意的v∈V(G),有|φ(NG(v))|≥min{dG(v),r}.

對于正整數(shù)k和r,稱χr(G)=min{k|G有一個(k,r)-染色}為G的r-動態(tài)色數(shù).

2001年,Montgomery[1]首次提出動態(tài)染色概念,并提出如下猜想：

猜想1[1]若圖G是正則圖,則χ2(G)≤χ(G)+2.

定理1[2]若圖G是正則圖,則χ2(G)≤2χ(G).

Montgomery[1]證明了猜想1對K1,3-free圖是成立的,Jahanbekam等[3]證明了猜想1對直徑為2的圖是成立的,且Akbari等[4]證明了猜想1對k-正則二部圖是成立的,其中k≥4.

Bowler等[5]構(gòu)造了χ1(G)=n(n≥2)、χ2(G)=2n的正則圖G,該例證明了猜想1是錯誤的,并且說明Alishahi[2]證明的定理1中關(guān)于2-動態(tài)色數(shù)是緊的.

對于無圍長限制的部分平面圖G,χr(G)的最新結(jié)果有:

定理2[6]對于任意平面圖G,有χ2(G)≤5.

定理3[7]對于任意連通平面圖G,除C5外,有χ2(G)≤4.

定理4[8]對于任意平面圖G,有χ3(G)≤10.

定理5[9]對于r≥8的平面圖G,有χr(G)≤2r+16.

文獻(xiàn)[10-14]還證明了部分平面圖χr(G)的上界，結(jié)果見表1.

表1 部分平面圖χr(G)的上界

本文將證明下面的定理:

定理6平面圖G是圍長g(G)≥5且5-圈與5-圈不相鄰的簡單圖,若r≥11,則χr(G)≤r+4.

1 記 號

對于V′?V,令G[V′]為G在V′上的導(dǎo)出子圖,若存在映射φ:V′→[k]是G[V′]上的一個(k,r)-染色,則稱φ是G關(guān)于G[V′]的部分(k,r)-染色.當(dāng)φ是G的部分(k,r)-染色時,對于v∈V-V′,令{φ(v)}=?,對于v∈V,定義如下顏色集φ[v]:

2 定理6的證明

下面利用極小反例和權(quán)轉(zhuǎn)移的方法證明定理6.設(shè)圖G是定理6中使得|V(G)|+|E(G)|最小的一個反例,即圖G是g(G)≥5且5-圈與5-圈不相鄰的平面圖,r≥11,χr(G)≥r+5,但對于G中的任意一條邊e,有χr(G-e)≤r+4.為了方便,記k=r+4.首先,G是連通的簡單平面圖.接下來探討G的結(jié)構(gòu)性質(zhì).

引理1對于平面圖G,有:

1)G是2-連通的;

2)G中的2-點(diǎn)與2-點(diǎn)不相鄰.

證明1)若v為G的一個割點(diǎn),令G1與G2是G中滿足V(G1)∩V(G2)={v}和G=G1∪G2的2個連通子圖,則由G的極小性知,Gi有一個(k,r)-染色φi(i=1,2).當(dāng)φ1(v)=φ2(v)時,若|φ1(NG1(v))∪φ2(NG2(v))|≥min{dG(v),r},則定義一個新的染色φ:V(G)→[k];當(dāng)u∈V(Gi)時,φ(u)=φi(u)(1≤i≤2).顯然,φ是G中一個(k,r)-染色.若|φ1(NG1(v))∪φ2(NG2(v))|

2)若G有2個相鄰的2-點(diǎn)u和v,記N(u)={v,u1},N(v)={u,v1},則由G的極小性知,G′=G-uv是(k,r)-可染的.除去u,v的顏色,因?yàn)閨F(u)|≤|φ[u1]∪{φ(v1)}|≤r+1

引理2輕點(diǎn)與輕點(diǎn)不相鄰.

證明若G有2個相鄰的輕點(diǎn)u和v,則由G的極小性知,G′=G-uv是(k,r)-可染的.除去u,v的顏色,因?yàn)閨F(u)|≤D(u)-1≤r+2,|F(v)|≤D(v)-1≤r+2,所以u,v可以重新染好,得到G的(k,r)-染色,矛盾.引理2證畢.

引理3對于圖G,有:

1)3-點(diǎn)v至多與1個2-點(diǎn)相鄰;

2)輕3-點(diǎn)與2-點(diǎn)及3(1)-點(diǎn)不相鄰;

3)3(1)-點(diǎn)與3(1)-點(diǎn)不相鄰.

證明1)若v與至少2個2-點(diǎn)v1和v2相鄰,則由G的極小性知,G′=G-vv1是(k,r)-可染的.除去v,v1的顏色,因?yàn)閨F(v)|≤|φ[v3]∪{φ(v11),φ(v2),φ(v21)}|≤r+3,|F(v1)|≤|φ[v11]∪{φ(v2),φ(v3)}|≤r+2,所以v,v1可依次重新染好,得到G的(k,r)-染色,矛盾.

2)若G中的輕3-點(diǎn)u和2-點(diǎn)v相鄰,記N(u)={v,u1,u2},N(v)={u,v1},d(u1)+d(u2)≤r+1,則由G的極小性知,G′=G-uv是(k,r)-可染的.除去u,v的顏色,因?yàn)閨F(u)|≤|φ[u1]∪φ[u2]∪{φ(v1)}|≤d(u1)+d(u2)+1≤r+2,|F(v)|≤|φ[v1]∪{φ(u1),φ(u2)}|≤r+2,所以u,v可重新染好,得到G的(k,r)-染色,矛盾.

若G中存在輕3-點(diǎn)u和3(1)-點(diǎn)v相鄰,記N(u)={v,u1,u2},N(v)={u,v1,v2},其中d(v1)=2,d(u1)+d(u2)≤r,則由G的極小性知,G′=G-vv1是(k,r)-可染的.除去v,u,v1的顏色,因?yàn)閨F(v)|≤|φ[v2]∪{φ(v11),φ(u1),φ(u2)}|≤r+3,|F(u)|≤|φ[u1]∪φ[u2]∪{φ(v2)}|≤d(u1)+d(u2)+1≤r+1,|F(v1)|≤|φ[v11]∪{φ(v2)}|≤r+1,所以v,u,v1可依次重新染好,得到G的(k,r)-染色,矛盾.

3)若3(1)-點(diǎn)u與3(1)-點(diǎn)v相鄰,其中N(u)={u1,u2,v},N(v)={v1,v2,u},d(u1)=d(v1)=2,N(u1)={u11,u},N(v1)={v11,v},則由G的極小性知,G′=G-uv是(k,r)-可染的.除去u,v,v1,u1的顏色,因?yàn)閨F(u)|≤|φ[u2]∪{φ(u11),φ(v2)}|≤r+2,|F(v)|≤|φ[v2]∪{φ(v11),φ(u2)}|≤r+2,所以u,v可以染好.此時|F(v1)|≤|φ[v11]∪{φ(v2),φ(u),φ(v)}|≤r+3,|F(u1)|≤|φ[u11]∪{φ(u2),φ(u),φ(v)}|≤r+3.若N(u1)∩N(v1)=?,則u1與v1可染相同的顏色,u1,v1可以染好,故得到G的(k,r)-染色,矛盾.當(dāng)u1,v1有公共鄰點(diǎn)u11=v11時,因?yàn)閨F(u1)|≤r+3,所以u1可以染好.若|φ(N(u11))|=|φ(N(v11))|≥r-1,則|φ(N(v11))|≥r,故φ[v11]={φ(v11)}.因?yàn)閨F(v1)|≤|φ[v11]∪{φ(v),φ(u),φ(v2)}|≤4,所以v1可以染好,得到G的(k,r)-染色,矛盾.若u1,v1有公共鄰點(diǎn)u11=v11且|φ(N(u11))|=|φ(N(v11))|≤r-2,則|F(v1)|≤|φ[v11]∪{φ(v2),φ(u),φ(v)}|≤r-2+3=r+1,|F(u1)|≤|φ[u11]∪{φ(u2),φ(u),φ(v)}|≤r-2+3=r+1.因此,u1,v1可以染好,得到G的(k,r)-染色,矛盾.引理3證畢.

引理4對于圖G,有:

1)輕4-點(diǎn)與2-點(diǎn)不相鄰;

2)4(3)-點(diǎn)與輕2-點(diǎn)不相鄰.

證明1)若G中存在輕4-點(diǎn)v,其中N(v)={v1,v2,v3,v4},d(v1)=2,N(v1)={v,v11},則由G的極小性知,G′=G-vv1是(k,r)-可染的.由于v為輕點(diǎn),故d(v2)+d(v3)+d(v4)≤r+1.除去v,v1的顏色,因?yàn)閨F(v1)|≤|φ[v11]∪{φ(v2),φ(v3),φ(v4)}|≤r+3,|F(v)|≤|φ[v2]∪φ[v3]∪φ[v4]∪{φ(v11)}|≤r+2,所以v1,v可以依次重新染好,得到G的(k,r)-染色,矛盾.

2)對于4(3)-點(diǎn)v,記N(v)={v1,v2,v3,v4},d(vi)=2 (i=1,2,3).若v1為輕2-點(diǎn),則d(v11)≤r-1.由G的極小性知,G′=G-vv1是(k,r)-可染的.現(xiàn)除去v,v2,v3,v1的顏色,因?yàn)閨F(v)|≤|φ[v4]∪{φ(v11),φ(v21),φ(v31)}|≤r+3,|F(v2)|≤|φ[v21]∪{φ(v4)}|≤r+1,|F(v3)|≤|φ[v31]∪{φ(v4)}|≤r+1,|F(v1)|≤|φ[v11]∪{φ(v4)}|≤d(v11)+1≤r,所以v,v2,v3,v1可依次重新染好,得到G的(k,r)-染色,矛盾.引理4證畢.

引理5對于5-點(diǎn)v,其中N(v)={v1,v2,v3,v4,v5},d(vi)=2,N(vi)={v,vi1}(i=1,2,3,4),若d(v5)≤6,則d(vi1)≥r-1(i=1,2,3,4).

證明假設(shè)d(v11)≤r-2,由G的極小性知,G′=G-vv1是(k,r)-可染的.現(xiàn)除去v2,v3,v4,v,v1的顏色,因?yàn)閨F(v2)|≤|φ[v21]∪{φ(v5)}|≤r+1,|F(v3)|≤|φ[v31]∪{φ(v3)}|≤r+1,|F(v4)|≤|φ[v41]∪{φ(v5)}|≤r+1,|F(v)|≤|φ[v5]∪{φ(v11),φ(v21),φ(v31),φ(v41)}|≤6+4≤r-1,|F(v1)|≤|φ[v11]∪{φ(v5)}|≤r-1,所以v2,v3,v4,v,v1可依次重新染好,得到G的(k,r)-染色,矛盾.引理5證畢.

引理6對于6-點(diǎn)v,其中N(v)={v1,v2,v3,v4,v5,v6},d(vi)=2,N(vi)={v,vi1}(i=1,2,3,4,5),若d(v6)≤6,則{v11,v21,v31,v41,v51}中至少有4個(r-2)+-點(diǎn).

證明若{v11,v21,v31,v41,v51}中至多有3個(r-2)+-點(diǎn),則{v11,v21,v31,v41,v51}中至少有2個(r-3)--點(diǎn).不妨假設(shè)d(v11)≤r-3,d(v21)≤r-3.由G的極小性知,G′=G-vv1是(k,r)-可染的.現(xiàn)除去v3,v4,v5,v,v1,v2的顏色，因?yàn)閨F(v3)|≤|φ[v31]∪{φ(v6)}|≤r+1,|F(v4)|≤|φ[v41]∪{φ(v6)}|≤r+1,|F(v5)|≤|φ[v51]∪{φ(v6)}|≤r+1,|F(v)|≤|{φ(v11),φ(v21),φ(v31),φ(v41),φ(v51)}∪φ[v6]|≤5+6≤r,|F(v1)|≤|φ[v11]∪{φ(v6)}|≤r-2,|F(v2)|≤|φ[v21]∪{φ(v6)}|≤r-2,所以v3,v4,v5,v,v1,v2可依次重新染好,得到G的(k,r)-染色,矛盾.引理6證畢.

該矛盾說明G不存在,從而定理6成立.為方便起見,用τ(S→u)表示S中元素給u轉(zhuǎn)的權(quán)值總和.下面是權(quán)轉(zhuǎn)移規(guī)則:

表2 d(v)≥10,5≤d(u)≤6,u與v弱相鄰,同時滿足條件1與2時,v給u轉(zhuǎn)移的權(quán)值

2)若5≤d(u)≤6,d(v)≥10,u與v弱相鄰,則當(dāng)v滿足下列條件之一時,稱頂點(diǎn)v為a-點(diǎn):

①n2(v)=d(v)-1且W(v)與N(v)中9+-點(diǎn)的個數(shù)均大于等于1;

②d(v)-4≤n2(v)≤d(v)-2且N(v)中9+-點(diǎn)的個數(shù)大于等于1;

③n2(v)≤d(v)-5.

3)若5≤d(u)≤6,d(v)≥10,u與v弱相鄰,則當(dāng)v滿足下列條件之一時,稱頂點(diǎn)v為c-點(diǎn):

①n2(v)=d(v)且W(v)中9+-點(diǎn)的個數(shù)大于等于2;

②n2(v)=d(v)-1且W(v)中9+-點(diǎn)的個數(shù)大于等于1,N(v)中無9+-點(diǎn);

③d(v)-4≤n2(v)≤d(v)-2且N(v)中無9+-點(diǎn).

1)d(v)=2,ω(v)=-2,記f1和f2為與v關(guān)聯(lián)的面.

3)d(v)=4,ω(v)=1.由引理4中1)知,n2(v)≤3.

①n2(v)=5.v為輕點(diǎn),由引理2知,vi為重點(diǎn),故d(vi1)≥r+4-5=r-1≥10(1≤i≤5).記f1,f2,f3,f4,f5為與v關(guān)聯(lián)的面.

5)d(v)=6,ω(v)=4.

7)d(v)=8,ω(v)=7.

綜上,得到了下面有矛盾的式子:

上面的矛盾說明G不存在,從而定理6是成立的.

3 結(jié) 語

本文在前人研究的基礎(chǔ)上,對平面圖的限制條件進(jìn)行了調(diào)整,進(jìn)而得到了更好的上界.平面圖在不同的限制條件下還有很多有意義的性質(zhì),因此,可以在這些性質(zhì)下進(jìn)一步研究平面圖的r-動態(tài)色數(shù),并得到一些更有意義的結(jié)果.