不含4-圈的平面圖的L( p, q)-標號

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

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

不含4-圈的平面圖的L(p,q)-標號

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

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

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

平面圖；4-圈；L(p,q)-標號

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

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

1,1

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

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

1 引理及其證明

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

（R1）每個5+?面f轉移權1/5給每個相關聯(lián)的點；

（R2）每個5?點u轉移權4/5給每個相鄰的2-點；

（R3）每個4+?點u轉移權1/5給每個相鄰的3-點；

（R4）每個4?點u轉移權1/5給每個相關聯(lián)的3-面；

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

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

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

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

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

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

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

2 定理1的證明

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

假設定理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包含滿足構型（A1）–（A10）之一的頂點u.假設u1,L ,uk為u的鄰點，且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）成立，不妨設d(x) =d(z) = 3，令H=G?ux.顯然，H是不含4-圈的平面圖，且 Δ (H) ≤Δ (G)，|E(H)|<|E(G)|.由于G的邊數(shù)的極小性，λp,q(H)≤n，因此H存在一個以L為標號集合的n?L(p,q)?標號.設該映射為φ，下面給G進行標號.

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

情形2 若（A2）成立，將φ限制到圖G上，因為|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的原有標號，依次給u1和u重新標號.設xi為u1的不同于u的鄰點，其中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).因為d(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的標號，然后依次給u和u1進行重新標號.由于 |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的標號，然后依次給u和x進行重新標號.設z,w為u的不同于x,y的鄰點.因為|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的標號，然后依次給u和x進行重新標號.因|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的標號，然后依次給u,u1,u2進行標號.因為 |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進行標號，因為|F(ui)|≤2(2p?1)+ (2q? 1)(Δ (G)?1 + 4)

情形8 若（A8）成立，將φ限制到圖G上.首先取消u,t,w的標號，然后依次給u,t,w重新標號.設z為u的不同于x,y,t,w的鄰點.因為|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進行標號，因為|F(t)|≤ 3(2p? 1)+(2q? 1)(5? 1+ 5? 1 +Δ (G)? 1)

情形9 若（A9）成立，將φ限制到圖G上，首先取消u,w的原有標號，然后依次給u,w重新標號.不妨設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進行標號，因為|F(w) |≤ 2(2p? 1)+(2q? 1)(5? 1 +Δ (G)? 1)

情形10 若（A10）成立，不妨設d(x) =d(z) = 3，令H=G?ux.設w為u的不同于x,y,z,t的鄰點.將φ限制到圖G上.首先取消u,x,z的標號，然后依次給u,x,z重新標號.因為|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)

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

[1]West D B. 圖論導引[M]. 李建中, 駱吉洲, 譯. 2版. 北京: 機械工業(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- )，男，吉林白城人，助教，碩士，研究方向：圖論與軍事運籌學