朱海洋，盛景軍，侯立峰，葛生聯(lián)

(徐州空軍學(xué)院后勤指揮系，江蘇徐州 221000)

不含4-圈的平面圖的L(p,q)-標(biāo)號(hào)

朱海洋，盛景軍，侯立峰，葛生聯(lián)

(徐州空軍學(xué)院后勤指揮系，江蘇徐州 221000)

令G為平面圖，用Δ(G)和λp,q(G)分別表示G的最大度和L(p,q)?標(biāo)號(hào)數(shù)，其中p和q是滿足p≥q的兩個(gè)正整數(shù).證明了若G為Δ(G)≤5且不含4-圈的平面圖，則λp,q(G) ≤ (2q?1)Δ (G)+ 8p+ 14q? 11.這一結(jié)論改進(jìn)了有關(guān)文獻(xiàn)的相關(guān)結(jié)果.

平面圖；4-圈；L(p,q)-標(biāo)號(hào)

所有圖均為無(wú)向連通簡(jiǎn)單圖.對(duì)于圖G，令V(G)、E(G)、Δ(G)和δ(G)分別為圖的頂點(diǎn)集合、邊集合、最大度和最小度，如果圖G能畫在曲面S上使它的邊僅在端點(diǎn)處相交，則稱G可嵌入曲面S.若圖G可嵌入平面，則稱G是平面圖.平圖是平面圖在平面上的一個(gè)嵌入.dG(u,v)表示頂點(diǎn)u,v之間的距離.圖G的圍長(zhǎng)g(G)是G中最短圈的長(zhǎng)度.圖G的平方圖記為G2，指的是一個(gè)圖滿足以下條件：V(G2) =V(G)并且uv∈E(G2)，當(dāng)且僅當(dāng)1≤dG(u,v) ≤ 2.圖G的正常k?頂點(diǎn)染色是映射f:V(G) → {1,L ,k}，其中f滿足對(duì)任意的相鄰頂點(diǎn)u,v，都有f(u) ≠f(v)，最小的整數(shù)k稱為圖G的色數(shù)，記為χ(G)，由 Brooks定理，對(duì)于任意圖G，χ(G2) ≤Δ2(G)+ 1，這個(gè)上界是緊的，Petersen圖和5-圈就是兩個(gè)最簡(jiǎn)單的例子.其它未定義的符號(hào)見(jiàn)文獻(xiàn)[1].

定義1 設(shè)p和q是滿足p≥q的兩個(gè)正整數(shù).圖G的k?L(p,q)?標(biāo)號(hào)是一個(gè)映射?:V(G) → {0,1, L,k} ，其中?滿足對(duì)任意的u,v∈V(G)，若dG(u,v) = 1，則p；若dG(u,v)= 2，則 |?(u)??(v)|≥q.圖G的L(p,q)?標(biāo)號(hào)數(shù)是使G存在k?L(p,q)?標(biāo)號(hào)的最小的整數(shù)k，記為λp,q(G).圖G的L(1,1)?標(biāo)號(hào)等價(jià)于圖G2的正常頂點(diǎn)染色，且λ(G)=χ(G2) ?1.

1,1

Wegner[2]首先研究了平面圖的平方圖的色數(shù)，證明了若G為 Δ (G) = 3的平面圖，則χ(G2) ≤ 8，并且提出以下著名猜想：

猜想1 設(shè)G為平面圖，若 4 ≤Δ (G)≤7，則χ(G2) ≤Δ (G)+5；若 Δ (G)≥8，則

1 引理及其證明

證明：假設(shè)引理1不正確，設(shè)G為 Δ (G)≤ 5且不含4-圈的平圖，為不含構(gòu)型（A1）–（A10）的一個(gè)反例.由于G無(wú)4-圈，所以G中不存在兩個(gè)相鄰3-面，且每個(gè)頂點(diǎn)u至多關(guān)聯(lián) ??d(u)/2??個(gè) 3-面.由于假設(shè)G不含構(gòu)型（A1）和（A2），所以δ(G) ≥ 2且G中任意3-面都不關(guān)聯(lián)任何2-點(diǎn).由假設(shè)G不含構(gòu)型（A3），所以G中不存在一條邊uv∈E(G)使d(u) = 2和d(v)≤4.由于假設(shè)G不含構(gòu)型（A4），所以G中不存在一條邊uv∈E(G)使d(u) =d(v) = 3.由于假設(shè)G不含構(gòu)型（A5），所以G中不存在一條關(guān)聯(lián)某個(gè) 3-面的邊uv∈E(G)使d(u)=4，d(v)=3.下面給出所使用的重新分配頂點(diǎn)和面的權(quán)轉(zhuǎn)移規(guī)則：

（R1）每個(gè)5+?面f轉(zhuǎn)移權(quán)1/5給每個(gè)相關(guān)聯(lián)的點(diǎn)；

（R2）每個(gè)5?點(diǎn)u轉(zhuǎn)移權(quán)4/5給每個(gè)相鄰的2-點(diǎn)；

（R3）每個(gè)4+?點(diǎn)u轉(zhuǎn)移權(quán)1/5給每個(gè)相鄰的3-點(diǎn)；

（R4）每個(gè)4?點(diǎn)u轉(zhuǎn)移權(quán)1/5給每個(gè)相關(guān)聯(lián)的3-面；

（R5）設(shè)u是一個(gè)5-點(diǎn)和f是它的關(guān)聯(lián)3-面.若f是一個(gè)(5,5,5)?面，則u轉(zhuǎn)移權(quán)1/3給f；否則u轉(zhuǎn)移權(quán)3/5給f.

設(shè)w′表示結(jié)果權(quán)函數(shù)，只需證明對(duì)任意的x∈V(G)UF(G)，均有w′(x)≥ 0.

下面首先考察任意面f∈F(G)的新權(quán).

情況3 若d(u)=4.設(shè)x,y,z,t是u的鄰點(diǎn).由于假設(shè)G不含（A3），所以x,y,z,t均為3+?點(diǎn).

情況 4 若d(u)=5.設(shè)x,y,z,t,w是u的鄰點(diǎn).由假設(shè)G不含（A7），所以u(píng)至多相鄰 2個(gè)2-點(diǎn).

情況4.2 假設(shè)u只關(guān)聯(lián)1個(gè)3-面，那么u關(guān)聯(lián)4個(gè)5+?面.不妨設(shè) [ ]f=uxy為該3-面.因?yàn)镚不含構(gòu)型（A2），所以x,y均為3+?點(diǎn).因?yàn)镚不含構(gòu)型（A4），所以{x,y}中至多存在1個(gè)3?點(diǎn).因?yàn)镚不含構(gòu)型（A8），所以{z,t,w}中至多存在1個(gè)2-點(diǎn).

情況4.3 假設(shè)u只關(guān)聯(lián)2個(gè)3-面，那么u關(guān)聯(lián)3個(gè)5+?面.不妨設(shè)f1=[uxy]和f2=[uzt]為關(guān)聯(lián)u的3-面.因?yàn)镚不含構(gòu)型（A2），所以x,y,z,t均為3+?點(diǎn).因?yàn)镚不含構(gòu)型（A4），所以{x,y}中至多存在1個(gè)3?點(diǎn)，{z,t}中至多存在1個(gè)3?點(diǎn).

2 定理1的證明

定理1的證明：采用反證法.

假設(shè)定理1不成立.選取G為滿足假定條件且λp,q(G)>n的邊數(shù)|E(G)|盡可能小的平面圖，其中n= (2q?1)Δ (G)+ 8p+ 14q? 11 = 4(2p?1)+ (2q?1)(Δ (G)+ 7).記L= {0,1,L ,n}.

由引理1知，G包含滿足構(gòu)型（A1）–（A10）之一的頂點(diǎn)u.假設(shè)u1,L ,uk為u的鄰點(diǎn)，且d(u1)≤d(u2) ≤L≤d(uk).若（A1）或（A2）成立，令H=G?u.若（A3）或（A4）或（A7）成立，令H=G?uu1.若（A5）或（A6）成立，令H=G?ux.若（A8）或（A9）成立，令H=G?uw.若（A10）成立，不妨設(shè)d(x) =d(z) = 3，令H=G?ux.顯然，H是不含4-圈的平面圖，且 Δ (H) ≤Δ (G)，|E(H)|<|E(G)|.由于G的邊數(shù)的極小性，λp,q(H)≤n，因此H存在一個(gè)以L為標(biāo)號(hào)集合的n?L(p,q)?標(biāo)號(hào).設(shè)該映射為φ，下面給G進(jìn)行標(biāo)號(hào).

情形1 若（A1）成立，將φ限制到圖G上.因?yàn)閨F(u)|≤ (2p?1)+ (2q?1)(Δ (G)?1)

情形2 若（A2）成立，將φ限制到圖G上，因?yàn)閨F(u)|≤ 2(2p?1)+ (2q? 1)(d(u1)?2+d(u2)?2) ≤ 2(2p?1)+ (2q? 1)(5 ?2 +Δ (G)?2)

情形 3 若（A3）成立，將φ限制到圖G上，現(xiàn)去掉u和u1的原有標(biāo)號(hào)，依次給u1和u重新標(biāo)號(hào).設(shè)xi為u1的不同于u的鄰點(diǎn)，其中i=1,L ,d(u1)?1.那么 |F(u1)|≤(d(u1)?1) (2p?1)+(2q? 1)(d(u)?1+d(x1)?1 +L+d(xd(u1)?1)?1).因?yàn)閐(u1) ≤ 4，所以 |F(u1)|≤3(2p?1)+ (2q? 1)(2? 1+ 5? 1+ 5? 1 +Δ (G)?1)≤n.令φ(u1)∈LF(u1).由于F(u)≤ 2(2q?1) + (2q? 1)(d(u1)?1 +d(u2)? 1) ≤ 2(2q?1)+ (2q? 1)(4? 1 +Δ (G)?1)

情形4 若（A4）成立，將φ限制到圖G上.首先去掉u和u1的標(biāo)號(hào)，然后依次給u和u1進(jìn)行重新標(biāo)號(hào).由于 |F(u)|≤ 2(2p?1)+(2q? 1)(∑i=1,2,3(d(ui)?1)) ≤ 2(2p?1)+(2q?1)(2 +4+ Δ (G)? 1)

情形5 若（A5）成立，將φ限制到圖G上.首先取消u和x的標(biāo)號(hào)，然后依次給u和x進(jìn)行重新標(biāo)號(hào).設(shè)z,w為u的不同于x,y的鄰點(diǎn).因?yàn)閨F(u)|≤ 3(2p?1) +(2q? 1)(d(x) ?2+d(y) ?2 +d(z)?1 +d(w) ?1) ≤ 3(2p?1) + (2q? 1)(3 ?2 +5 ?2 +5 ?1 +Δ (G)?1)

情形6 若（A6）成立，將φ限制到圖G上.首先取消u和x的標(biāo)號(hào)，然后依次給u和x進(jìn)行重新標(biāo)號(hào).因|F(u)|≤ 3(2p?1)+ (2q? 1)(d(x) ?2 +d(y) ?2 +5? 1 +Δ (G)?1) ≤ 3(2p?1)+ (2q? 1)(2 +2 +4 +Δ (G)?1)

情形7 若（A7）成立，將φ限制到圖G上.首先取消u,u1,u2的標(biāo)號(hào)，然后依次給u,u1,u2進(jìn)行標(biāo)號(hào).因?yàn)?|F(u)|≤ 3(2p?1)+(2q? 1)(∑i=1,L,5(d(ui)?1)) ≤ 3(2p?1)+(2q?1)(1+ 1+ 3+ 4 +Δ (G)? 1) ≤n，令φ(u)∈LF(u).其次給u1,u2進(jìn)行標(biāo)號(hào)，因?yàn)閨F(ui)|≤2(2p?1)+ (2q? 1)(Δ (G)?1 + 4)

情形8 若（A8）成立，將φ限制到圖G上.首先取消u,t,w的標(biāo)號(hào)，然后依次給u,t,w重新標(biāo)號(hào).設(shè)z為u的不同于x,y,t,w的鄰點(diǎn).因?yàn)閨F(u)|≤ 3(2p?1) +(2q? 1)(d(x) ?2 +d(y)?2 +d(t) ?1 +d(w) ?1 +d(z) ?1) ≤ 3(2p?1)+ (2q? 1)(3 +3 +2+ 1 +Δ (G)?1)≤n，令φ(u)∈LF(u).其次給t進(jìn)行標(biāo)號(hào)，因?yàn)閨F(t)|≤ 3(2p? 1)+(2q? 1)(5? 1+ 5? 1 +Δ (G)? 1)

情形9 若（A9）成立，將φ限制到圖G上，首先取消u,w的原有標(biāo)號(hào)，然后依次給u,w重新標(biāo)號(hào).不妨設(shè)d(x)≤4.由于|F(u)|≤ 4(2p?1) + (2q? 1)(d(x) ?2 +d(y) ?2 +d(t) ?2+d(z)? 2+d(w)? 1)≤4(2p?1)+ (2q? 1)(2 +3 +3 +Δ (G)?2+ 1)=n，令φ(u)∈LF(u).最后給w進(jìn)行標(biāo)號(hào)，因?yàn)閨F(w) |≤ 2(2p? 1)+(2q? 1)(5? 1 +Δ (G)? 1)

情形10 若（A10）成立，不妨設(shè)d(x) =d(z) = 3，令H=G?ux.設(shè)w為u的不同于x,y,z,t的鄰點(diǎn).將φ限制到圖G上.首先取消u,x,z的標(biāo)號(hào)，然后依次給u,x,z重新標(biāo)號(hào).因?yàn)閨F(u)|≤ 3(2p?1)+(2q? 1)(d(x) ?2 +d(y) ?2 +d(t) ?2 +d(z) ?2 +d(w) ?1) ≤ 3(2p?1)+ (2q? 1)(1+ 3 +3+ 1 +Δ (G)? 1)

這樣，每一種情況φ都可以擴(kuò)展到G的以L為標(biāo)號(hào)集合的n?L(p,q)?標(biāo)號(hào)，所以λp,q(G)≤n，這與λp,q(G)>n相矛盾.證畢.

[1]West D B. 圖論導(dǎo)引[M]. 李建中, 駱吉洲, 譯. 2版. 北京: 機(jī)械工業(yè)出版社, 2006: 10-20.

[2]Wegner G. Graphs with given diameter and coloring problem [R]. Dortmund: Department of Mathematics, University of Dortmund, 1977: 1-10.

[3]Thomassen C. Applications of Tutte cycles [R]. Copenhagen: Department of Mathematics, Technical University of Denmark, 2001: 1-20.

[4]Heuvel J V D, Mcguiness S. Coloring the square of a planar graph [J]. Journal of Graph Theory, 2003, 42: 110-124.

[5]Molly M, Salanatipour M R. A bound on the chromatic number of the square of a planar graph [J]. Journal of Combinatorial Theory: B, 2005, 94: 189-213.

[6]Wang W F, Lih K W. Labeling planar graphs with conditions on girth and distance two [J]. SIAM Journal on Discrete Mathematics, 2003, 17(2): 264-275.

[7]Wang W F, Cai L Z. Labeling planar graphs without 4-cycles with a condition on distance two [J]. Discrete Applied Mathematics, 2008, 156: 2241-2249.

[8]Borodin O V, Ivanova A O. 2-distance (Δ+2)-coloring of planar graphs with girth six and Δ (G)≥ 18 [J]. Discrete Mathematics, 2009, 309: 6496-6502.

L(p,q)-Labeling of Planar Graphs without 4-Cycles

ZHU Haiyang, SHENG Jingjun, HOU Lifeng, GE Shenglian
(Department of Logistics Command, Xuzhou Air Force College of PLA, Xuzhou, China 221000)

LetGbe a planar graph,p,qbe two positive integers withp≥q, Δ(G) andλp,q(G) denote respectively the maximum degree and theL(p,q)-labeling number ofG. Then,λp,q(G)≤ (2q? 1) Δ (G)+ 8p+ 14q? 11 could be achieved ifGbe a planar graph with Δ (G) ≤ 5 and without 4-cycles. The result improves previous results for the planar graphGwith Δ (G) ≤ 5 and without 4-cycles.

Planar Graph; 4-Cycles;L(p,q)-Labeling

(編輯：王一芳)

O157.5

A

1674-3563(2011)02-0019-08

10.3875/j.issn.1674-3563.2011.02.004 本文的PDF文件可以從xuebao.wzu.edu.cn獲得

2010-07-05

朱海洋(1979- )，男，吉林白城人，助教，碩士，研究方向：圖論與軍事運(yùn)籌學(xué)