外平面圖的距離2-點可區(qū)別邊色數(shù)*

王維凡,王琰雯,黃丹君

(浙江師范大學 數(shù)理與信息工程學院,浙江 金華 321004)

?

外平面圖的距離2-點可區(qū)別邊色數(shù)*

王維凡,王琰雯,黃丹君

(浙江師范大學 數(shù)理與信息工程學院,浙江 金華 321004)

邊染色;距離2-點可區(qū)別邊染色;外平面圖;最大度

0 引 言

本文考慮的圖都是有限簡單圖.設V(G),E(G),Δ(G),δ(G)分別表示圖G的頂點集、邊集、最大度和最小度.用NG(v)表示與頂點v相鄰的點集合,因此,dG(v)=|NG(v)|是v在圖G中的度.用dG(u,v)表示2個點u和v在G中的距離,即連接它們的最短路的長度.在不引起混淆的情況下,分別將Δ(G),NG(v),dG(v),dG(u,v)簡記為Δ,N(v),d(v),d(u,v).一個k-點(k+-點或k--點)是一個度數(shù)為k(至多為k,或者至少為k)的點.對i≥1,用ni(v)表示與點v相鄰的i-點的個數(shù)．若一個圖G沒有孤立邊,就稱它是正常的.圖G的一個正常k-邊染色是指一個映射φ:E(G)→{1,2,…,k},使得相鄰的邊染不同的顏色.對于一個點v∈V(G),用Cφ(v)表示所有與v相關(guān)聯(lián)的邊得到的顏色集合,即Cφ(v)={φ(uv) |uv∈E(G)}.

本文研究外平面圖族的距離2-點可區(qū)別邊染色問題,證明了:任意外平面圖G的距離2-點可區(qū)別的邊色數(shù)不超過2Δ.

1 結(jié)構(gòu)引理

若一個圖能嵌入到歐幾里得平面上,使得所有點都出現(xiàn)在無界面的邊界上,則稱這個圖為外可平面圖.外平面圖是外可平面圖在歐幾里得平面上的一個嵌入.設G是一個外平面圖,用F(G)表示G中面的集合.對于f∈F(G),用b(f)表示f的邊界,并且若u1,u2,…,un是b(f)上沿順時針方向的點,則記f=[u1u2…un].一個度為1的頂點也稱為一個葉子.

為了刻畫外平面圖的邊-面全色數(shù),王維凡等[11]證明了下面的結(jié)構(gòu)引理：

引理1 設G是一個外平面圖,且δ(G)=2,那么G必含有下面子構(gòu)型之一(見圖 1):

1)一條路x1x2x3x4滿足d(x2)=d(x3)=2;

2)一個3-面[uv1v2]滿足d(u)=2,d(v1)=3;

3)2個3-面[xu1v1]和[xu2v2]滿足d(u1)=d(u2)=2,d(x)=4.

(a) (b) (c) 圖1 引理1中G的3個子圖

圖1中,若與一個點相關(guān)聯(lián)的邊都畫出來了,也即這個點的度數(shù)確定了,就用實心點來表示;否則,就用空心點來表示.

引理2 每一個至少有2個頂點的連通圖G必含有下面的子構(gòu)型之一:

1)一個度數(shù)至多為3的頂點v與葉子相鄰,或者一個4+-點v至多相鄰于2個非葉子點;

2)一條路x1x2x3x4滿足d(x2)=d(x3)=2;

3)一個3-面[uv1v2]滿足d(u)=2,d(v1)≥3且n1(v1)=d(v1)-3;

4)2個3-面[xu1v1]和[xu2v2]滿足d(u1)=d(u2)=2,d(x)≥4和n1(x)=d(x)-4.

證明 采用反證法.假設G不包含1)～4)中任意一個.因為G不含有1),所以G沒有3--點相鄰于葉子,而且每一個4+-點v至多與d(v)-3個葉子相鄰,也就是說它至少有3個鄰點不是葉子.

設H是由G去掉所有葉子之后得到的圖,那么H是一個連通的外平面圖.設v∈V(H),因為V(H)?V(G),所以由H的定義可知dG(v)≥2.若2≤dG(v)≤3,則dH(v)=dG(v)≥2;若dG(v)≥4,則dH(v)=dG(v)-n1(v)≥dG(v)-(dG(v)-3)=3.因此,δ(H)=2.由引理1知,H包含圖1 中的子圖形 (a),(b)和(c)之一.注意到：若dH(v)=2,則dG(v)=2.所以,容易觀察到G至少包含引理2中的2),3)和4)之一,與G的假設相矛盾.引理2證畢.

下面2個引理是很容易被證明成立的:

引理3 設Pn是一條長為n≥2的路,則

引理4 設Cn是一個長為n≥3的圈,則

2 主要結(jié)果

1)G包含一個3--點v,使得n1(v)≥1;或者G包含一個4+-點 v,使得n1(v)≥k-2,即為引理2中的1).

設v1,v2,…,vk是v的鄰點,其中k=d(v)且v1是G的一個葉子.下面分為2個子情形.

②k≥4.那么n1(v)≥k-2.假設d(vi)=1,i=1,2,…,k-2,且令H=G-{v1,v2,…,vk-2}.則由歸納假設知,H有一個應用顏色集合C的距離2-點可區(qū)別邊染色φ.不失一般性,設φ(vvk-1)=1,φ(vvk)=2.注意到點v至多有2Δ-2個距離為2的點.由于

所以一定存在一個(k-2)-元子集 C′?C{φ(vv1),φ(vv2)},使得vv1,vv2,…,vvk-2可以應用集合C′進行合法染色.因此,可得到圖G的一個距離2-點可區(qū)別2Δ-邊染色.

2)G包含一條路x1x2x3x4,使得d(x2)=d(x3)=2,即為引理2中的2).

如果x1與x4重合,那么圖G-x2x3有一個應用顏色集合C的距離2-點可區(qū)別邊染色φ.由于x2x3有2個禁用色,且x2,x3至多有Δ-2個距離為2的頂點,|C|=2Δ,因此可以對x2x3進行合法染色,從而得到圖G的一個距離2-點可區(qū)別2Δ-邊染色.

下面假設x1≠x4.設H是由圖G通過收縮邊x2x3成為一個新點w后而得到的圖,那么H是一個滿足|T(H)|<|T(G)|的簡單外平面圖.由歸納假設,H有一個應用顏色集合C的距離2點可區(qū)別邊染色φ,使得φ(wx1)=1且φ(wx4)=2.基于φ,在圖G中,把x1x2染成顏色1,把x3x4染成顏色2.若x2x3不能被合法染色,則d(x1)=d(x4)=Δ,Cφ(yi)={1,2+i},i=1,2,…,Δ-1,且Cφ(zj)={2,Δ+1+j},j=1,2,…,Δ-1,其中y1,y2,…,yΔ-1是x1的不同于x2的鄰點,z1,z2,…,zΔ-1是x4的不同于x3的鄰點.因此,φ(x1yi)=2+i 且φ(x4zj)=Δ+1+j.把x1x2改染成2,把x2x3染成1,由此就得到圖G的一個距離2-點可區(qū)別2Δ-邊染色.

3)G包含一個3-面[uv1v2]滿足d(u)=2,d(v1)=k≥3和n1(v1)=k-3,即為引理2中的3).

基于2)的證明,可以假設d(v2)≥3.設u,w,v2,x1,x2,…,xk-3是v1的鄰點,其中d(x1)=d(x2)=…=d(xk-3)=1.下面分為2種子情形.

①k≥4.設H=G-{x1,x2,…,xk-3}.由歸納假設知,H有一個應用顏色集合C的距離2-點可區(qū)別邊染色φ,使得φ(wv1)=1,φ(v1v2)=2及φ(uv1)=3.注意到v1至多有(Δ-1)+(Δ-2)=2Δ-3個距離為2的k-點.若k≥5,則由

知,一定存在一個(k-3)-元子集C′?{4,5,…,2Δ},使得v1x1,v1x2,…,v1xk-3可以應用顏色集合C′進行合法染色,這樣就得到了圖G的一個距離2-點可區(qū)別2Δ-邊染色.因此,下面假設k=4.若v1x1不能夠被合法染色,那么對所有的i=4,5,…,2Δ,{1,2,3,i}是v1的某個距離為2且度數(shù)為4的頂點的顏色集合.所以,v1的所有距離為2的點都是4-點.在{4,5}{φ(uv2)}中選取一個顏色來改染v1u,然后把v1x1染成顏色6即可.

②k=3.令 H=G-uv1.由歸納假設知,H有一個應用顏色集合C的距離2-點可區(qū)別邊染色φ,使得φ(uv2)=1,φ(v1v2)=2和φ(wv1)=a.先設d(w)=2.若a=1,則u和v1總共至多有Δ個距離為2的點.因為Δ≥3且|C{1,2}|=2Δ-2>Δ,所以可以在C{1,2}中選取一個顏色對uv1進行合法染色.若 a≠1,不妨設a=3,則只要用{4,5,2Δ}給邊uv1正常染色,u與w的顏色集合就不同.故u和v1總共至多有Δ-1個距離為2的點.因為Δ≥3且|C{1,2,3}|=2Δ-3>Δ-1,所以可以在C{1,2,3}中選取一個顏色對uv1進行合法染色.這樣就得到了圖G一個距離2-點可區(qū)別2Δ-邊染色.

現(xiàn)在,假設d(w)≥3,那么在圖G中,u和v1總共至多有(Δ-1)+(Δ-2)=2Δ-3個沖突點.若a=1,則|C{1,2}|=2Δ-2>2Δ-3,可以在C{1,2}中選取一個顏色對uv1進行合法染色.所以,下面假設a≠1,不妨設a=3.若 uv1不能夠被合法染色,則假設{{2,3,i} | i=4,5,…,Δ+2}={Cφ(x)|x∈N(w){v1}},且{2,3,j}或{1,j}(j=Δ+3,Δ+4,…,2Δ)是v2的某些鄰點的顏色集合.在這種情況下,把uv2和v1v2的顏色互換,把uv1染成顏色4即可.

4)G包含2個3-面[xu1v1]和[xu2v2]滿足d(u1)=d(u2)=2,d(x)=k≥4和n1(x)=k-4,即為引理2中的4).

基于2)的證明,可以假設d(v1)≥3且d(v2)≥3.設y1,y2,…,yd(v1)-2是v1的不同于x和u1的鄰點,z1,z2,…,zd(v2)-2是v2的不同于x和u2的鄰點.同時,用x1,x2,…,xk-4表示x的不同于u1,u2,v1,v2的鄰點.由定義知,對所有的i=1,2,…,k-4,都有d(xi)=1.需要討論下面2種可能性:

①k≥5.設H=G-{x1,x2,…,xk-4}.由歸納假設知,H有一個應用顏色集合C的距離2-點可區(qū)別邊染色φ,使得φ(xv1)=1,φ(xu1)=2,φ(xu2)=3及φ(xv2)=4.注意到x至多有2(Δ-2)=2Δ-4個距離為2的k-點.若k≥6,則由

知,存在一個(k-4)-元子集C′?C{1,2,3,4},使得xx1,xx2,…,xxk-4可以使用顏色集合C′進行合法染色.因此,下面假設k=5.若 xx1不能夠被合法染色,則d(v1)=d(v2)=Δ,且對每一個i=5,6,…,2Δ,{1,2,3,4,i}是{y1,y2,…,yΔ-2,z1,z2,…,zΔ-2}中的一個頂點的顏色集合,這就意味著{y1,y2,…,yΔ-2,z1,z2,…,zΔ-2}中的每一個點都是5-點.為了得到圖G的一個距離2-點可區(qū)別2Δ-邊染色,只需在{5,6}{φ(v1u1)}中選取一個顏色改染xu1,然后把xx1染成顏色7即可.

②k=4.由歸納假設知,G-xu1有一個應用顏色集合C的距離2-點可區(qū)別邊染色φ,使得φ(xv1)=1,φ(xu2)=2,φ(xv2)=3,φ(u1v1)=a.注意到a≠1,因此,需要考慮下面2種情況.

i)a∈{2,3}.

易見,x和u1在圖G中總共至多有2Δ-3 個沖突點.若xu1不能夠被合法染色,則d(v1)=d(v2)=Δ.進而進一步假設:Cφ(u2)={2,4};Cφ(zi)={1,2,3,i+4},i=1,2,…,Δ-2;Cφ(yi)={a,i+Δ+2}或者{1,2,3,i+Δ+2},i=1,2,…,Δ-2.所以φ(u2v2)=4.互換u2v2和xv2的顏色,然后把xu1染成顏色5,就得到了圖G的一個距離2-點可區(qū)別2Δ-邊染色.

ii)a?{2,3},令 a=4.

若xu1能夠被正常染色,則u1和u2將得到不同的顏色集合.此外,x和u1在圖G中總共至多有2Δ-4個沖突點.若xu1不能夠被合法染色,則推出d(v1)=d(v2)=Δ,且可以假設Cφ(zi)={1,2,3,i+4},i=1,2,…,Δ-2;Cφ(yi)={a,i+Δ+2}或者{1,2,3,i+Δ+2},i=1,2,…,Δ-2.這時可以把u1v1和xv1的顏色互換,然后把xu1染成顏色5,就得到了G的一個距離2-點可區(qū)別2Δ-邊染色.定理1證畢.

[1]Akbari S,Bidkhori N,Nosrati N.r-Strong edge colorings of graphs[J].Discrete Math,2006,306(23):3005-3010.

[2]Zhang Zhongfu,Li Jingwen,Chen Xiangen,et al.D(β)-vertex-distinguishing proper edge-coloring of graphs[J].Acta Math Sinica:Chin Ser,2006,49(3):703-708.

[5]Bazgan C,Harkat-Benhamdine A H,Li Hao,et al.On the vertex-distinguishing proper edge-colorings of graphs[J].J Combin Theory Ser B,1999,75(2):288-301.

[6]Burris A C,Schelp R H.Vertex-distinguishing proper edge-colorings[J].J Graph Theory,1997,26(2):73-82.

[7]Zhang Zhongfu,Liu Linzhong,Wang Jianfang.Adjacent strong edge coloring of graphs[J].Appl Math Lett,2002,15(5):623-626.

[8]Balister P N,Gy?ri E,Lehel J,et al.Adjacent vertex distinguishing edge-colorings[J].SIAM J Discrete Math,2007,21(1):237-250.

[9]Hatami H.Δ+300 is a bound on the the adjacent vertex distinguishing edge chromatic number[J].J Combin Theory Ser B,2005,95(2):246-256.

[10]Horňák M,Huang Danjun,Wang Weifan.On neighbor-distinguishing index of planar graphs[J].J Graph Theory,2014,76(4):262-278.

[11]Wang Weifan,Zhang Kemin.Δ-matchings and edge-face chromatic numbers[J].Acta Math Appl Sin,1999,22(2):236-242.

(責任編輯 陶立方)

Distance vertex-distinguishing index of outerplanar graphs

WANG Weifan,WANG Yanwen,HUANG Danjun

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,Jinhua321004,China)

edgecoloring; 2-distance vertex-distinguishing index; outerplanar graph; maximum degree

10.16218/j.issn.1001-5051.2016.01.001

??2015-05-27；

2015-09-02

國家自然科學基金資助項目(11371328;11301486)

王維凡(1955-)，男，遼寧沈陽人，教授，博導.研究方向：圖論與組合優(yōu)化.

O157.5

A

1001-5051(2016)01-001-05