最大度為5的簡單圖的2-距離列表染色*

卜月華, 王麗霞

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

0 引 言

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

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

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

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

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

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

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

文獻[7]證明下面的定理:

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

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

定理4[8]對最大度Δ=5的簡單圖G,有:

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

定理5對最大度Δ≤5的簡單圖G,有:

1 定理 5 的證明

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

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

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

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

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

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

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

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

(1)

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

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

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

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

性質(zhì)5k-點(2≤k≤5)至多與k-2個2-點相鄰.

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

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

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

性質(zhì)7設(shè)3(0)-點v的鄰域為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個小于9,不妨設(shè)d(v11)+d(v12)≤8,則由圖G的極小性知,對于G′=G-vv1的列表配置L,G′是L-2-距離可染的.擦去v,v1的顏色并進行重染.因為|F(v1)|≤d(v11)+d(v12)+2≤10,所以可令c(v1)∈L(v)c(N2(v1),從而可以將v1染好.此時,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個不超過8,不妨設(shè)d(v11)+d(v12)≤8.由圖G的極小性知,G′=G-vv1是L-2-距離可染的.擦去v,v1的顏色并進行重染.因為|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的顏色并進行重染.因為|F(v)|≤d(v3)+3+2=10,所以可以將v染好.此時,因為d(v11)+d(v12)≤7,所以|F(v1)|≤7+3=10,從而可以將v1染好.這與G是引理2的極小反例矛盾.性質(zhì)7證畢.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2)當5(2)-點v與1個4(2)-點或3(1)-點相鄰時,有d(v4)+d(v5)≥8;

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

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

1)若5(2)-點v相鄰2個4(2)-點v3,v4,則由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v,v2,v3,v4及N(v3),N(v4)中2-點的顏色.由于|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.此時,N(v3)中2-點的禁用色至多為Δ(G)+3≤8,故可以將N(v3)中的2-點染好.最后,因為N(v4)中的2-點的禁用色至多為Δ(G)+3≤8,所以仍可以將N(v4)中的2-點染好.因此,G是L-2-距離可染的.矛盾.同樣可證其他幾種情況.

2)設(shè)5(2)-點v相鄰1個4(2)-點或3(1)-點v3且d(v4)+d(v5)≤7,則由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v,v1,v2,v3及N(v3)中2-點的顏色.因為|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.此時,因為N(v3)中的每個2-點的禁用色至多是Δ(G)+3≤8,所以可以將N(v3)中的2-點染好,從而G是L-2-距離可染的.矛盾.

3)若5(2)-點v相鄰1個3(1)-點v3和1個1-型的3(0)-點v4,則由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v,v2,v3,v4及N(v3)中2-點的顏色.因為|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.最后,因為N(v3)中2-點的禁用色至多為Δ(G)+3≤8,從而G是L-2-距離可染的.這與G的假設(shè)矛盾.性質(zhì)13證畢.

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

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

若5(1)-點v與2個3(1)-點v2,v3相鄰且d(v4)+d(v5)≤7(為方便,記v的2-鄰點為v1),則由圖G的極小性知,G′=G-v1是L-2-距離可染的.擦去v,v2,v3及N(v2),N(v3)中2-點的顏色.因為|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.此時,N(v2),N(v3)中2-點的禁用色至多是Δ(G)+3≤8,所以G是L-2-距離可染的.這與G的假設(shè)矛盾.性質(zhì)14證畢.

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

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

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

(2)

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

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

②v是3(0)-點.

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

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

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

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

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

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

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

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

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

2 結(jié) 語

參考文獻：

[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).