卜月華, 王麗霞

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

0 引 言

對(duì)于圖的2-距離色數(shù),1977年,Wegner[1]提出了關(guān)于其上界的一個(gè)著名的猜想:

猜想1[1]對(duì)最大度為Δ的平面圖G,有:

Wegner還給出了:若猜想1成立,則上界是可達(dá)的.Tomassen利用圖的分解和四色定理證明了猜想1對(duì)于Δ=3的情況成立,但是目前對(duì)于Δ≥4的情況仍未解決.

文獻(xiàn)[3]給出下列結(jié)論：

定理1[3]對(duì)最大度為Δ≥8 821且g(G)≥6的平面圖G,有χ2(G)≤Δ(G)+2.

文獻(xiàn)[4]將定理1改進(jìn)到以下結(jié)論：

定理2[4]對(duì)最大度為Δ≥18且g(G)≥6的平面圖G,有χ2(G)≤Δ(G)+2.

文獻(xiàn)[7]證明下面的定理:

定理3[7]對(duì)最大度Δ=4的圖G,下列結(jié)論成立:

文獻(xiàn)[8]研究了Δ(G)=5的圖的2-距離染色,有下列結(jié)論:

定理4[8]對(duì)最大度Δ=5的簡(jiǎn)單圖G,有:

筆者改進(jìn)了定理 4中4)的結(jié)果,主要得到下列結(jié)果:

定理5對(duì)最大度Δ≤5的簡(jiǎn)單圖G,有:

1 定理 5 的證明

對(duì)于G的一個(gè)2-距離染色(或G的部分2-距離染色)c,設(shè)V1?V(G),記c(V1)={c(v)|v∈V1}.用F(v)表示頂點(diǎn)v的禁用色集合,顯然有F(v)=c(N2(v)),則|F(v)|≤|N2(v)|≤|D(v)|.由于定理5的2個(gè)結(jié)果相互獨(dú)立,因此,可作為2個(gè)引理來證明.

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

證明 反證法.若存在1-點(diǎn)v,記uv∈E(G),則根據(jù)圖G的極小性知,G′=G-v有一個(gè)L-2-距離染色c′.因?yàn)閨F(v)|≤|D(v)|=d(u)≤Δ(G),所以可令c(v)∈L(v)c(N2(v)),u∈V(G-v),c(u)=c′(u),從而G是一個(gè)L-2-距離可染的.矛盾.性質(zhì)1證畢.

性質(zhì)2k-點(diǎn)(2≤k≤4)至多與k-2個(gè)2-點(diǎn)相鄰.

證明 設(shè)k-點(diǎn)v與k-1個(gè)2-點(diǎn)相鄰(不妨設(shè)d(v1)=d(v2)=…=d(vk-1)=2,d(vk)≥3),則由圖G的極小性知,G′=G-v是L-2-距離可染的.擦去v1,v2,…,vk-1的顏色并進(jìn)行重染.因?yàn)閨F(v)|≤Δ(G)+k-1≤8,所以可以將v染好.此時(shí)|F(vi)|≤Δ(G)+1+1≤7(1≤i≤k-1).因此,可依次染好v1,v2,…,vk-1.從而G是L-2-距離可染的.矛盾.性質(zhì)2證畢.

性質(zhì)3若3-點(diǎn)v與1個(gè)2-點(diǎn)v1相鄰,則v的另外2個(gè)鄰點(diǎn)v2,v3滿足d(v2)+d(v3)≥9.

證明 反證法.假設(shè)d(v2)+d(v3)<9,則由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v的顏色并進(jìn)行重染.由于d(v2)+d(v3)<9,所以|F(v)|≤d(v2)+d(v3)+1≤8+1=9,從而可以將頂點(diǎn)v染好.此時(shí),|F(v1)|≤Δ(G)+3≤8,所以G是L-2-距離可染的.這與G是引理1的反例矛盾.性質(zhì)3證畢.

下面利用權(quán)轉(zhuǎn)移的方法證明G是不存在的,從而完成引理1的證明.給每個(gè)頂點(diǎn)v定義初始權(quán)μ(v)=d(v),則

(1)

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

與式(1)矛盾.引理 1 證畢.

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

證明 與性質(zhì)1的證明一樣.故略.

性質(zhì)5k-點(diǎn)(2≤k≤5)至多與k-2個(gè)2-點(diǎn)相鄰.

證明 與性質(zhì)2的證明類似.故略.

性質(zhì)6若3-點(diǎn)v與1個(gè)2-點(diǎn)v1相鄰,則v的另外2個(gè)鄰點(diǎn)v2,v3都是Δ-點(diǎn).

證明 反證法.若v2,v3中至少有一個(gè)(Δ-1)-點(diǎn),不妨設(shè)d(v2)≤Δ(G)-1,則由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v的顏色并進(jìn)行重染.由于d(v2)+d(v3)≤9,從而|F(v)|≤d(v2)+d(v3)+1≤9+1=10,所以可以將頂點(diǎn)v染好.此時(shí),|F(v1)|≤Δ(G)+3≤8,所以也可以將v1染好.從而G是L-2-距離可染的.這與G的假設(shè)矛盾.性質(zhì)6證畢.

性質(zhì)7設(shè)3(0)-點(diǎn)v的鄰域?yàn)镹(v)={v1,v2,v3},則

1)若d(v1)=d(v2)=d(v3)=3,則d(vi1)+d(vi2)≥9(i=1,2,3);

2)若d(v1)=d(v2)=3,d(v3)=4,則d(v11)+d(v12)+d(v21)+d(v22)≥18;

3)若d(v1)=d(v2)=3,d(v3)=5,則d(vi1)+d(vi2)≥8(i=1,2).

證明 1)若d(vi1)+d(vi2)(i=1,2,3)中至少有1個(gè)小于9,不妨設(shè)d(v11)+d(v12)≤8,則由圖G的極小性知,對(duì)于G′=G-vv1的列表配置L,G′是L-2-距離可染的.擦去v,v1的顏色并進(jìn)行重染.因?yàn)閨F(v1)|≤d(v11)+d(v12)+2≤10,所以可令c(v1)∈L(v)c(N2(v1),從而可以將v1染好.此時(shí),v的禁用色至多為9,所以可以將v染好.因此，G是L-2-距離可染的.矛盾.

2)若d(v11)+d(v12)+d(v21)+d(v22)≤17,則d(v11)+d(v12)和d(v21)+d(v22)中至少有1個(gè)不超過8,不妨設(shè)d(v11)+d(v12)≤8.由圖G的極小性知,G′=G-vv1是L-2-距離可染的.擦去v,v1的顏色并進(jìn)行重染.因?yàn)閨F(v1)|≤d(v11)+d(v12)+2≤8+2=10,|F(v)|≤4+3+2=9,所以可以依次染好v1,v,從而圖G是L-2-距離可染的.矛盾.

3)不妨設(shè)d(v11)+d(v12)≤7,由圖G的極小性知,G′=G-vv1是L-2-距離可染的.擦去v,v1的顏色并進(jìn)行重染.因?yàn)閨F(v)|≤d(v3)+3+2=10,所以可以將v染好.此時(shí),因?yàn)閐(v11)+d(v12)≤7,所以|F(v1)|≤7+3=10,從而可以將v1染好.這與G是引理2的極小反例矛盾.性質(zhì)7證畢.

性質(zhì)8若4-點(diǎn)v與2個(gè)2-點(diǎn)v1,v2相鄰,則d(v3)+d(v4)≥9,且4(2)-點(diǎn)不與4(2)-點(diǎn)相鄰.

證明 若d(v3)+d(v4)≤8,則由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v,v2的顏色并進(jìn)行重染.因?yàn)閨F(v)|≤8+2=10,所以可以將v染好.此時(shí),|F(vi)|≤Δ(G)+4≤9(i=1,2),從而可以將v1,v2染好.與G是引理2的極小反例矛盾.

若4(2)-點(diǎn)v與1個(gè)4(2)-點(diǎn)v3相鄰,記與v3相鄰的2個(gè)2-點(diǎn)為v31,v32.由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v,v3,v31,v32的顏色并進(jìn)行重染.先討論頂點(diǎn)v和v3的禁用色.因?yàn)閨F(v)|≤Δ(G)+1+2+1≤9,|F(v3)|≤Δ(G)+2+2≤9,所以可以將v和v3染好.此時(shí),2-點(diǎn)v1,v31和v32的禁用色分別不超過Δ(G)+4,Δ(G)+3,Δ(G)+3,從而G是L-2-距離可染的.矛盾.性質(zhì)8證畢.

性質(zhì)94(1)-點(diǎn)v至多與1個(gè)4(2)-點(diǎn)相鄰.若4(1)-點(diǎn)v與1個(gè)4(2)-點(diǎn)相鄰,記此點(diǎn)為v2,則d(v3)+d(v4)≥9.

證明 設(shè)4-點(diǎn)v的鄰域?yàn)镹(v)={v1,v2,v3,v4}.若v1是2-點(diǎn),v2,v3是4(2)-點(diǎn),則由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v,v2,v3及N(v2),N(v3)中2-點(diǎn)的顏色并進(jìn)行重染.因?yàn)閨F(v)|≤Δ(G)+3≤8,|F(vi)|≤Δ(G)+2+1≤8(i=2,3),所以可以將v,v2,v3依次染好.此時(shí),|F(v1)|≤Δ(G)+4≤9,因此,可以將v1重新染好.最后,因?yàn)镹(vi) (i=2,3)中2-點(diǎn)的禁用色至多為Δ(G)+3≤8(若N(v2)和N(v2)中有2個(gè)2-點(diǎn)的距離小于等于2,則這2個(gè)2-點(diǎn)的可用色相應(yīng)增加),所以可以將N(v2)和N(v3)中的2-點(diǎn)重染好,從而G是L-2-距離可染的.這與G的假設(shè)矛盾.

設(shè)4(1)-點(diǎn)v相鄰2-點(diǎn)v1和4(2)-點(diǎn)v2,但是d(v3)+d(v4)≤8,記v2的2個(gè)2-鄰點(diǎn)為v21,v22.由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v,v2,v21,v22的顏色并進(jìn)行重染.因?yàn)閨F(v)|≤d(v3)+d(v4)+2≤8+2=10,|F(v2)|≤Δ(G)+2+2≤9,所以可以依次染好v,v2.此時(shí),|F(v1)|≤Δ(G)+4≤9,因此可以將v1染好.因?yàn)関21,v22的禁用色都不超過Δ(G)+3≤8,所以v21,v22可以被染好，從而G是L-2-距離可染的.矛盾.因此,d(v3)+d(v4)≥9.性質(zhì)9證畢.

性質(zhì)101)4(1)-點(diǎn)v至少與1個(gè)4+-點(diǎn)相鄰;當(dāng)4(1)-點(diǎn)v恰好與2個(gè)3(0)-點(diǎn)v2,v3相鄰時(shí),v2和v3只能是i-型3(0)-點(diǎn)和j-型3(0)-點(diǎn),其中i+j≤2.

2)若4(1)-點(diǎn)v與2個(gè)1-型的3(0)-點(diǎn)v2,v3相鄰,其中v2,v3不同于v的鄰點(diǎn)分別記為v2i,v3i(i=1,2),d(v21)=d(v31)=3,則d(v22)=d(v32)=Δ.

證明 1)若4(1)-點(diǎn)v與3個(gè)3-點(diǎn)v2,v3,v4相鄰,則由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去頂點(diǎn)v的顏色并進(jìn)行重染.因?yàn)閨F(v)|≤3×3+1=10,|F(v1)|≤Δ(G)+3=8,所以可以依次染好v,v1,從而G是L-2-距離可染的.矛盾.

若與4(1)-點(diǎn)v相鄰的2個(gè)3(0)-點(diǎn)中一個(gè)是1-型的3(0)-點(diǎn)v2,另一個(gè)是2-型的3(0)-點(diǎn)v3,則由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v,v2,v3的顏色并進(jìn)行重染.因?yàn)閨F(v)|≤Δ(G)+1+2+2≤10,所以可以將v染好.此時(shí)|F(v2)|≤Δ(G)+3+2≤10,|F(v3)|≤3+3+2=8,故可以依次將v2,v3染好.最后,因?yàn)閨F(v1)|≤Δ(G)+4≤9,所以圖G是L-2-距離可染的.矛盾.其他情況類似可證.

2)當(dāng)4(1)-點(diǎn)v與2個(gè)1-型的3(0)-點(diǎn)v2,v3相鄰時(shí),若d(v22)+d(v32)<2Δ,則可設(shè)d(v22)≤Δ-1.由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v,v2,v3的顏色并進(jìn)行重染.因?yàn)閨F(v)|≤Δ(G)+1+2+2=10,所以可以將v染好.此時(shí),|F(v3)|≤Δ(G)+3+2=10,|F(v2)|≤Δ(G)-1+2+3≤9,故可以依次染好v3,v2.最后,因?yàn)閨F(v)|≤Δ(G)+4≤9,所以圖G是L-2-距離可染的.矛盾.性質(zhì)10證畢.

性質(zhì)11設(shè)v為4(0)-點(diǎn),N(v)={v1,v2,v3,v4},則N(v)中至多有3個(gè)4(2)-點(diǎn).若N(v)中恰好有3個(gè)4(2)-點(diǎn),則v的另一個(gè)鄰點(diǎn)v4及vi(i=1,2,3)的另一個(gè)鄰點(diǎn)都是Δ-點(diǎn).

證明 若4(0)-點(diǎn)v與4個(gè)4(2)-點(diǎn)v1,v2,v3,v4相鄰,則由圖G的極小性知,G′=G-v是L-2-距離可染的.擦去v1,v2,v3,v4及N2(v)中2-點(diǎn)的顏色并進(jìn)行重染.由于|F(vi)|≤Δ(G)+2≤7(i=1,2,3,4),所以可以依次染好v1,v2,v3,v4.此時(shí),|F(v)|≤4×2=8,故也可以將v染好.最后,由于N2(v)中2-點(diǎn)的禁用色都不超過Δ(G)+3≤8,所以可以將未著色的2-點(diǎn)都染好，從而G是L-2-距離可染的.矛盾.

若N(v)中恰好有3個(gè)4(2)-點(diǎn),但是v的另一個(gè)鄰點(diǎn)v4或vi(i=1,2,3)的另一個(gè)鄰點(diǎn)中有一個(gè)不是Δ-點(diǎn),不妨設(shè)d(v4)≤Δ(G)-1.由圖G的極小性知,G′=G-v是L-2-距離可染的.擦去v1,v2,v3和N(vi)(i=1,2,3)中2-點(diǎn)的顏色并進(jìn)行重染.因?yàn)閨F(vi)|≤Δ(G)+2≤7(i=1,2,3),所以可以依次染好v1,v2,v3.此時(shí),|F(v)|≤(Δ(G)-1)+2×3≤10,故可以染好v.最后,由于N(vi)(i=1,2,3)中2-點(diǎn)的禁用色至多為Δ(G)+3≤8,所以可以將它們都染好,從而圖G是L-2-距離可染的.這與圖G的假設(shè)矛盾.其他幾種情況類似可證.性質(zhì)11證畢.

性質(zhì)12若5-點(diǎn)v與3個(gè)2-點(diǎn)相鄰,則d(v4)+d(v5)≥8,即v4,v5是5-點(diǎn)與3+-點(diǎn)或者都是4+-點(diǎn),且v不再與5(3)-點(diǎn)、3(1)-點(diǎn)、4(2)-點(diǎn)、i-型的3(0)-點(diǎn)相鄰(i=1,2).

證明 設(shè)5(3)-點(diǎn)v的2-鄰點(diǎn)分別為v1,v2,v3.

若d(v4)+d(v5)<8,則由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v,v2,v3的顏色并進(jìn)行重染.因?yàn)閨F(v)|≤d(v4)+d(v5)+3≤7+3=10,所以可以將v染好.此時(shí),|F(vi)|≤Δ(G)+3≤8(i=1,2,3),從而G是L-2-距離可染的.這與G的假設(shè)矛盾.

若5(3)-點(diǎn)v與5(3)-點(diǎn)v4相鄰,則由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v,v1,v2,v3,v4和N(v4)中2-點(diǎn)的顏色并進(jìn)行重染.由于|F(v)|≤Δ(G)+3+1≤9,|F(v4)|≤Δ(G)+4≤9,所以可以依次將v和v4染好.此時(shí),|F(vi)|≤Δ(G)+3≤8,故可以將vi染好(i=1,2,3).最后,因?yàn)镹(v4)中每個(gè)2-點(diǎn)的禁用色至多是Δ(G)+3≤8,從而G是L-2-距離可染的.這與G的假設(shè)矛盾.

類似地,可以證明5(3)-點(diǎn)v不與4(2)-點(diǎn)、3(1)-點(diǎn)相鄰.

下面將證明5(3)-點(diǎn)v不與i-型的3(0)-點(diǎn)相鄰(i=1,2).

設(shè)5(3)-點(diǎn)v與1-型的3(0)-點(diǎn)v4相鄰,為方便,記v4的3-鄰點(diǎn)為v41,v的2-鄰點(diǎn)為v1,v2,v3.由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v,v4,v2,v3的顏色并進(jìn)行重染.因?yàn)閨F(v)|≤Δ(G)+3+2≤10,|F(v4)|≤Δ(G)+3+1≤9,所以可以染好v和v4.此時(shí),|F(vi)|≤Δ(G)+3≤8(i=1,2,3),從而G是L-2-距離可染的.矛盾.同樣可以證明5(3)-點(diǎn)不與2-型3(0)-點(diǎn)相鄰.性質(zhì)12證明.

性質(zhì)131)5(2)-點(diǎn)v至多與1個(gè)4(2)-點(diǎn)或3(1)-點(diǎn)相鄰且5(2)-點(diǎn)不同時(shí)與3(1)-點(diǎn)和4(2)-點(diǎn)相鄰;

2)當(dāng)5(2)-點(diǎn)v與1個(gè)4(2)-點(diǎn)或3(1)-點(diǎn)相鄰時(shí),有d(v4)+d(v5)≥8;

3)5(2)-點(diǎn)不同時(shí)與3(1)-點(diǎn)和i-型3(0)-點(diǎn)(i=1或2)相鄰.

證明 設(shè)與5(2)-點(diǎn)v相鄰的2個(gè)2-點(diǎn)為v1,v2.

1)若5(2)-點(diǎn)v相鄰2個(gè)4(2)-點(diǎn)v3,v4,則由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v,v2,v3,v4及N(v3),N(v4)中2-點(diǎn)的顏色.由于|F(v)|≤Δ(G)+4≤9,|F(vi)|≤Δ(G)+3≤8(i=3,4),|F(vi)|≤Δ(G)+1(i=1,2),所以可以依次染好v,v3,v4,v1,v2.此時(shí),N(v3)中2-點(diǎn)的禁用色至多為Δ(G)+3≤8,故可以將N(v3)中的2-點(diǎn)染好.最后,因?yàn)镹(v4)中的2-點(diǎn)的禁用色至多為Δ(G)+3≤8,所以仍可以將N(v4)中的2-點(diǎn)染好.因此,G是L-2-距離可染的.矛盾.同樣可證其他幾種情況.

2)設(shè)5(2)-點(diǎn)v相鄰1個(gè)4(2)-點(diǎn)或3(1)-點(diǎn)v3且d(v4)+d(v5)≤7,則由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v,v1,v2,v3及N(v3)中2-點(diǎn)的顏色.因?yàn)閨F(v)|≤d(v4)+d(v5)+3≤7+3=10,|F(v3)|≤Δ(G)+2+2≤9,|F(vi)|≤Δ(G)+2≤7(i=1,2),所以可以依次染好v,v3,v1,v2.此時(shí),因?yàn)镹(v3)中的每個(gè)2-點(diǎn)的禁用色至多是Δ(G)+3≤8,所以可以將N(v3)中的2-點(diǎn)染好,從而G是L-2-距離可染的.矛盾.

3)若5(2)-點(diǎn)v相鄰1個(gè)3(1)-點(diǎn)v3和1個(gè)1-型的3(0)-點(diǎn)v4,則由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v,v2,v3,v4及N(v3)中2-點(diǎn)的顏色.因?yàn)閨F(v)|≤Δ(G)+3+2=10,|F(v4)|≤Δ(G)+4≤9,|F(v3)|≤Δ(G)+2≤7,|F(vi)|≤Δ(G)+1(i=1,2),所以可以依次染好v,v4,v3,v1,v2.最后,因?yàn)镹(v3)中2-點(diǎn)的禁用色至多為Δ(G)+3≤8,從而G是L-2-距離可染的.這與G的假設(shè)矛盾.性質(zhì)13證畢.

性質(zhì)145(1)-點(diǎn)v至多與2個(gè)3(1)-點(diǎn)相鄰.當(dāng)5(1)-點(diǎn)v與2個(gè)3(1)-點(diǎn)v2,v3相鄰時(shí),d(v4)+d(v5)≥8,即v4,v5都是4+-點(diǎn)或者是5-點(diǎn)與3+-點(diǎn).

證明 5(1)-點(diǎn)至多與2個(gè)3(1)-點(diǎn)相鄰的證明與5(2)-點(diǎn)至多與1個(gè)3(1)-點(diǎn)相鄰的證明類似.故略.

若5(1)-點(diǎn)v與2個(gè)3(1)-點(diǎn)v2,v3相鄰且d(v4)+d(v5)≤7(為方便,記v的2-鄰點(diǎn)為v1),則由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v,v2,v3及N(v2),N(v3)中2-點(diǎn)的顏色.因?yàn)閨F(v)|≤d(v4)+d(v5)+3≤7+3=10,|F(vi)|≤Δ(G)+1+2=8(i=2,3),|F(v1)|≤Δ(G)+2≤7,所以可以先染好v,再染好v2,v3,v1.此時(shí),N(v2),N(v3)中2-點(diǎn)的禁用色至多是Δ(G)+3≤8,所以G是L-2-距離可染的.這與G的假設(shè)矛盾.性質(zhì)14證畢.

性質(zhì)155(0)-點(diǎn)至多與4個(gè)3(1)-點(diǎn)相鄰.

證明 若5(0)-點(diǎn)v與5個(gè)3(1)-點(diǎn)相鄰(為方便,記v1,v2,v3,v4,v5為v的5個(gè)3(1)-鄰點(diǎn),vi1為vi的2-鄰點(diǎn)(i=1,2,3,4,5)),則由圖G的極小性知,G′=G-v是L-2-距離可染的.擦去vi,vi1(i=1,2,3,4,5)的顏色并進(jìn)行重染.因?yàn)閨F(vi)|≤Δ(G)+1≤6(i=1,2,3,4,5),所以可以依次染好v1,v2,v3,v4,v5.此時(shí),因?yàn)閨F(v)|≤2×5=10,所以可以將v染好.最后,因?yàn)閨F(vi1)|≤Δ(G)+3≤8(i=1,2,3,4,5),所以可以染好N2(v)中的2-點(diǎn)v11,v21,v31,v41,v51,從而圖G是L-2-距離可染的.矛盾.性質(zhì)15證畢.

接下來利用權(quán)轉(zhuǎn)移的方法證明G不存在,從而完成引理2的證明.給每個(gè)點(diǎn)一個(gè)初始權(quán)μ(v)=d(v),則

(2)

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

2)d(v)=3.由性質(zhì)5知,v至多相鄰1個(gè) 2-點(diǎn).

②v是3(0)-點(diǎn).

3)d(v)=4.由性質(zhì)5知,v至多與2個(gè)2-點(diǎn)相鄰.考慮下面幾種情況：

②v是4(1)-點(diǎn).由性質(zhì)10知,v至少與1個(gè) 4+-點(diǎn)相鄰.

③v是4(0)-點(diǎn).由性質(zhì)11知,v至多與3個(gè)4(2)-點(diǎn)相鄰.

4)d(v)=5.由性質(zhì)5知,v至多相鄰3個(gè)2-點(diǎn).考慮下列情況:

①v是5(3)-點(diǎn).由性質(zhì)12知,d(v4)+d(v5)≥8.

②v是5(2)-點(diǎn).由性質(zhì)13中的1)知,v至多與1個(gè)3(1)-點(diǎn)或4(2)-點(diǎn)相鄰.

③v是5(1)-點(diǎn).由性質(zhì)14知,v至多與2個(gè)3(1)-點(diǎn)相鄰.

與式(2)矛盾.引理2證畢.

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

2 結(jié) 語

參考文獻(xiàn)：

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

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

[4]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.

[5]Bonamy M,Lévêque B,Pinlou A.Graphs with maximum degreeΔ≥17 and maximum average degree less than 3 are list 2-distance (Δ+2)-colorable[J].Discreten Math,2014,317:19-32.

[6]Cranston D W,krekovski R.Sufficient sparseness conditions forG2to be (Δ+1)-choosable whenΔ≥ 5[J].Discrete Appl Math,2014,162(10):167-176.

[7]Cranston D W,Erman R,krekovski R.Choosability of the square of a planar graph with maximum degree four [J].Australas J Combin,2014,59(1):86-97.

[8]Bu Yuehua,Lü Xia,Yan Xiaoyan.The list 2-distance coloring of a graph withΔ(G)=5[J].Discrete Mathematics,Algorithms and Applications,2015,7(2):1550017(11).