嚴(yán)曉燕， 卜月華

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

0 引 言

本文僅考慮無向簡單圖.給定一個圖G,用V(G),E(G),Δ(G),δ(G),g(G)和dG(u,v)分別表示圖G的頂點集、邊集、最大度、最小度、圍長及G中頂點u,v間的距離.對x∈V(G),用dG(x)表示G中x的度,簡記為d(x).若d(v)=k(或d(v)≥k,或d(v)≤k),則稱v為一個k-點(或k+-點,或k--點).對平面圖G,用F(G)表示G的面的集合,并且可以類似地定義k-面,k--面,k+-面.

圖G的k-2-距離染色是指映射c:V(G)→{1,2,…,k},使得對G中滿足0

關(guān)于平面圖的2-距離染色,文獻(xiàn)[1]提出了如下猜想:

對于2-距離列表染色,文獻(xiàn)[10]提出了如下猜想:

定理1 若平面圖G滿足Δ(G)≤5,則下列結(jié)論成立:

1 符號說明

設(shè)v∈V(G),用NG(v)表示G中v的鄰點集合,nk(v)表示與v相鄰的k-點的個數(shù).稱與2-點相鄰的3-點為星.對于圖G中的頂點v,設(shè)v1,v2,…,vd(v)為v的鄰點,不妨設(shè)d(v1)≤d(v2)≤…≤d(vd(v)).用(d(v1),d(v2),…,d(vd(v)))表示v.為方便,也用鄰點的名字來代替其度數(shù),例如,4-點(2,2,x,y)表示這個4-點的鄰點為2個2-點及x和y,且d(x)≤d(y).對于圖G的一個頂點染色c,v∈V(G),令C(v)={c(u) | u∈V(G),0

2 定理1的證明

因為定理1的3個部分是完全獨立的,所以將分3個引理來證明.

性質(zhì)1 δ(G)≥2.

性質(zhì)2 G不含相鄰2-點.

證明 假設(shè)G含有相鄰2-點.不妨設(shè)uv∈E(G)且d(u)=d(v)=2.由G的極小性知,G-uv有一個L-2-距離染色.抹去u,v的顏色,則u,v的禁用色個數(shù)均至多為6,故u,v可以被重新染好.因此,G是L-2-距離可染的.得到矛盾.性質(zhì)2證畢.

性質(zhì)3 若3-點v為(2,x,y)-星,則x,y均為5-點.

證明 假設(shè)d(x)+d(y)≤9,且設(shè)與v相鄰的2-點為u.由G的極小性知,G-uv有一個L-2-距離染色.現(xiàn)將u,v的顏色抹去,則v的禁用色至多有10個,故可將v染好.此時,u的禁用色至多有8個,也可以將u重新染好,從而G是L-2-距離可染的.矛盾.因此,d(x)+d(y)≥10,但因Δ(G)≤5,故x,y均為5-點.性質(zhì)3證畢.

性質(zhì)4 若4-點v為(2,2,x,y)-點,則d(x)+d(y)≥9.

證明 假設(shè)u,w是與v相鄰的2個2-點,且設(shè)d(x)+d(y)≤8.由G的極小性知,G-uv有一個L-2-距離染色C′.現(xiàn)將u,v,w的顏色抹去,則v的禁用色個數(shù)至多為10,可以將v染好.此時,u,w的禁用色個數(shù)分別至多為8,所以u,v各至少有3種不同的顏色可以用.因此,可以將C′推廣為G的L-2-距離染色.矛盾.性質(zhì)4證畢.

由性質(zhì)4可知,4-點至多與2個2-點相鄰.

性質(zhì)5 若5-點v為(2,2,2,x,y)-點,則d(x)+d(y)≥8.

證明 假設(shè)與v相鄰的一個2-點為u,且設(shè)d(x)+d(y)≤7.由G的極小性可知,G-uv有一個L-2-距離染色.現(xiàn)抹去v和N(v)中3個2-點的顏色,則v的禁用色個數(shù)至多為10,可以將v重新染好.此時,3個2-點的禁用色個數(shù)各至多為8,那么至少有3種不同的顏色可以將3個2-點同時染好.因此,G是L-2-距離可染的.矛盾.性質(zhì)5證畢.

由性質(zhì)5可知,5-點至多與3個2-點相鄰.

現(xiàn)在將運(yùn)用權(quán)轉(zhuǎn)移的方法導(dǎo)出矛盾,從而完成引理1的證明.

(1)

(2)

上述矛盾說明G不存在,故可得引理1成立.

定義如下的權(quán)轉(zhuǎn)移規(guī)則:

R1:2-點從每個鄰點獲得權(quán)1;

因為g(G)≥6,所以d(f)≥6.又因為面不發(fā)生權(quán)轉(zhuǎn)移,所以w′(f)=w(f)=d(f)-6≥0.

下面分4種情形驗證w′(v)≥0,?v∈V(G).

1)d(v)=2.

根據(jù)性質(zhì)2可知,v相鄰2個3+-點.再由R1知,

w′(v)≥ 2×2-6+1×2=0.

2)d(v)=3.

w′(v)≥ 2×3-6=0.

3)d(v)=4.

由性質(zhì)4知,n2(v)≤2.由R1知,

w′(v)≥2×4-6-1×n2(v)=2-n2(v)≥

2-2=0.

4)d(v)=5.

由性質(zhì)5知,n2(v)≤3.由R1,R2知,

w′(v)≥2×5-6-1×n2(v)-

這樣,對任意x∈V∪F,都有w′(x)≥0,從而式(2)成立.矛盾.引理1證畢.

性質(zhì)6 δ(G)≥2.

性質(zhì)7 G不含相鄰2-點.

性質(zhì)6和性質(zhì)7與性質(zhì)1、性質(zhì)2類似,證略.

性質(zhì)8 若3-點v為(2,x,y)-星,則d(x)+d(y)≥8.

證明 假設(shè)與v相鄰的2-點為u，且設(shè)d(x)+d(y)≤7.由G的極小性知,G-uv有一個L-2-距離染色.抹去u,v的顏色,可知v的禁用色至多有8個,故可將v重新染好.此時,u的禁用色至多有8個.所以,也可以將u重新染好.從而G是L-2-距離列表可染的.矛盾.性質(zhì)8證畢.

性質(zhì)9 4-點至多與3個2-點相鄰.

證明 假設(shè)4-點與4個2-點相鄰,且設(shè)u是與v相鄰的一個2-點.由G的極小性知,G-uv有一個L-2-距離染色.現(xiàn)將v和N(v)中2-點的顏色抹去,則N(v)中2-點的禁用色個數(shù)各至多為5,故至少有4種不同的顏色可以將4個2-點同時染好.此時,v的禁用色個數(shù)至多為8,所以v也可以染好.因此，G是L-2-距離可染的.矛盾.性質(zhì)9證畢.

性質(zhì)10 若4-點v為(2,2,2,x)-點,則x不為星.

證明 假設(shè)x是星(如圖1所示的構(gòu)型H).由G的極小性知,G-vx有一個L-2-距離列表染色.抹去v,x,N(x)中的2-點和N(v)中的2-點的顏色.頂點x的禁用色個數(shù)至多為6,則x可以重新染好.此時,N(v)中2-點的禁用色個數(shù)分別至多為6,故至少有3種不同的顏色可以將N(v)中的3個2-點同時染好.這時,v至多有8種禁用色,所以v也可以染好.最后對N(x)中的2-點進(jìn)行重染.因為N(x)中2-點的禁用色個數(shù)至多為8,所以也可以染好.因此,G是L-2-距離可染的.矛盾.性質(zhì)10證畢.

圖1 構(gòu)型H

下面將運(yùn)用權(quán)轉(zhuǎn)移的方法,導(dǎo)出矛盾,從而完成引理2的證明.

對于連通平面圖G,根據(jù)Euler公式

|V|+|F|-|E|=2

和

有

(3)

(4)

定義的權(quán)轉(zhuǎn)移規(guī)則如下:

R3:2-點從相鄰的3+-點獲得權(quán)1;

顯然,對每個 f∈F,d(f)≥7.因為面不發(fā)生權(quán)轉(zhuǎn)移,所以

w′(f)=w(f)=d(f)-7≥0.

下面分4種情形驗證對每個v∈V(G), w′(v)≥0.

1)d(v)=2.

根據(jù)性質(zhì)7知,v相鄰2個3+-點.由R3知,

2)d(v)=3.

由性質(zhì)8知,n2(v)≤1.

①n2(v)=1.

此時v為(2,x,y)-星,則由性質(zhì)8知,d(x)+d(y)≥8,故v為(2,3,5)-點或為(2,4+,4+)-點.若v為(2,3,5)-點,則由R3,R4知,

若v為(2,4+,4+)-點,則由R3,R4,R5知,

②n2(v)=0.

v不發(fā)生權(quán)轉(zhuǎn)移,故

3)d(v)=4.

由性質(zhì)9知,n2(v)≤3.

①n2(v)=3.

由性質(zhì)10知,v不與星相鄰,則v只轉(zhuǎn)權(quán)給相鄰的2-點.由R3知,

②n2(v)≤2.

與v相鄰的星的個數(shù)至多為4-n2(v).由R3,R4知,

4)d(v)=5.

由R3,R4知,v轉(zhuǎn)給每個鄰點的權(quán)至多是1,則

這樣,對任意x∈V∪F,都有w′(x)≥0,從而式(4)成立.矛盾.故引理2成立.

性質(zhì)11 δ(G)≥2.

性質(zhì)12 G不含相鄰2-點.

性質(zhì)13 若3-點v為(2,2,x)-點,則d(x)≥4.

證明 假設(shè)與v相鄰的2個2-點分別為u,w，且設(shè)d(x)≤3.由G的極小性可知,G-uv有一個L-2-距離染色.抹去u,w,v的顏色,可知u,w的禁用色各至多有6個,則至少有2種不同的顏色可以將u,w染好.此時,v的禁用色至多有7個.所以,也可以將v重新染好,從而G是L-2-距離可染的.矛盾.性質(zhì)13證畢.

根據(jù)連通平面圖的Euler公式|V|+|F|-|E|=2及度和公式

對平面圖G,有

(5)

(6)

定義的權(quán)轉(zhuǎn)移規(guī)則如下:

R6:2-點從每個鄰點分別獲得權(quán)1;

R7:3-點從相鄰的4+-點獲得權(quán)1.

首先,因為g(G)≥ 8,所以對每個f∈F,d(f)≥8.因為面不發(fā)生權(quán)轉(zhuǎn)移,所以

w′(f)=w(f)=d(f)-8≥0.

下面分3種情況驗證:對每個v∈V(G),都有w′(v)≥0.

1)d(v)=2.

由性質(zhì)12知,v相鄰2個3+-點.由R6知,

w′(v)≥ 3×2-8+1×2=0.

2)d(v)=3.

由性質(zhì)13知,n2(v)≤2.

①n2(v)=2.

由性質(zhì)13知,v相鄰一個4+-點.由R6,R7知,

w′(v)≥ 3×3-8-2×1+1=0.

②n2(v)≤1.

v只給相鄰的2-點轉(zhuǎn)權(quán)1,則由R6知,

w′(v)≥ 3×3-8-n2(v)×1=

1-n2(v)≥1-1=0.

3)4≤d(v)≤5.

由R6,R7知,v給鄰點轉(zhuǎn)的權(quán)至多為1,則

w′(v)≥3×d(v)-8-d(v)×1=

2d(v)-8≥2×4-8=0.

至此,證明了對每個v∈V(G),w′(v)≥0.得到矛盾.引理3證畢.

綜合引理1、引理2和引理3的結(jié)論,完成定理1的證明.

[1]Wegner G.Graphs with given diameter and a coloring problem[R].Dortmund:University of Dortmund,1977.

[2]Molloy M,Salavatipour M R.A bound on the chromatic number of the square of a planar graph[J].J Combin Theory Ser:B,2005,94(2):189-213.

[3]Havet F,Van den Heuvel J,McDiarmid C,et al.List colouring squares of planar graphs[J].Electronic Notes in Discrete Math,2007,29:515-519.

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

[6]Borodin O V,Ivanova A O.List 2-distance(Δ+2)-coloring of planar graphs with girth six[J].European J Combin,2009,50(6):1216-1224.

[7]Bonamy M.Graphs with maximum degreeΔ≥17 and maximum average degree less than 3 are list 2-distance (Δ+2)-colorable[J].Discrete Mathematics,2013,313:427-449.

[8]Lih K W,Wang Weifan,Zhu Xuding.Coloring the square of ak4-minor free graph[J].Discrete Math,2003,269(1/2/3):303-309.

[9]Hetherington T J,Woodall D R.List-coloring the square of ak4-minor free graph[J].Discrete Math,2008,308(18):4037-4043.

[10]Kostochka A V,Woodall D R.Choosability conjecture and multicircuits[J].Discrete Math,2001,240(1/2/3):123-143.

[12]Montassier M,Raspaud A.A note on 2-facial coloring of plane graphs[J].Inf Process Lett,2006,98(6):211-266.

[13]Havet F.Choosability of the square of planar subcubic graphs with large girth[J].Discrete Math,2009,309(11):3553-3563.

[14]Cranston D W,Kim S J.List-coloring the square of a subcubic graph[J].J Graph Theory,2008,57(1):65-87.