無相鄰3-圈平面圖的鄰點(diǎn)可區(qū)別邊染色

蔡洪鋒, 黃丹君

(浙江師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,浙江 金華 321004)

0 引 言

Zhang等[1]在2002年提出圖的鄰點(diǎn)可區(qū)別邊染色這一概念,并對(duì)一些特殊圖類(樹、路、圈、完全圖、完全二部圖等)的鄰點(diǎn)可區(qū)別邊色數(shù)進(jìn)行了刻畫.基于這些結(jié)果,他們給出了關(guān)于圖的鄰點(diǎn)可區(qū)別邊染色問題的猜想.

1 定理1的證明

假設(shè)G是定理1中關(guān)于邊數(shù)達(dá)到最小的一個(gè)極小反例.顯然,G是連通的.先分析G的結(jié)構(gòu)性質(zhì),再運(yùn)用權(quán)轉(zhuǎn)移方法得出矛盾,從而定理1得證.令T(G)=max{10,Δ(G)+2},C={1,2,…,T(G)}表示顏色集合.顯然|C|≥10.

斷言1[15]圖G中1-點(diǎn)不與5--點(diǎn)相鄰.

注2設(shè)uv∈E(G)為G中的輕k-邊,k∈{2,3,4}.若H=G-uv存在一個(gè)T(G)-avd-邊染色φ且Cφ(u)≠Cφ(v),則|C(Cφ(u)∪Cφ(v))|≥10-2(k-1)≥4.由斷言2知,?α∈C(Cφ(u)∪Cφ(v)),使得邊uv可染α色且滿足u不與NG(u)中的點(diǎn)沖突,v不與v的鄰點(diǎn)沖突.因此,可以將φ擴(kuò)染為G的一個(gè)T(G)-avd-邊染色.

證明記NG(v)={v1,v2,…,vk},NG(v1)={v,v2,u1,u2}且NG(v2)={v,v1,w1,w2}.令H=G-v1v2.由注1知,H有一個(gè)T(G)-avd-邊染色φ.設(shè)φ(vvi)=i,i∈[1,k].

先證:若G中存在(4,4,k)-圈v1v2vv1,則k≥7.用反證法.假設(shè)k≤6.由斷言2和斷言3知,k=6.由注2知,Cφ(v1)=Cφ(v2).不妨設(shè)Cφ(v1)=Cφ(v2)={1,2,a}且a∈[3,7].可以用{8,9,10}中的任意一種顏色改染vv1或vv2,導(dǎo)出v的6個(gè)不同的顏色集合，而v至多只有4個(gè)沖突點(diǎn)，所以必存在一種改染方式φ′,使得v不與其鄰點(diǎn)產(chǎn)生沖突且Cφ′(v1)≠Cφ′(v2).由注2知,φ可以擴(kuò)染為G的一個(gè)T(G)-avd-邊染色.矛盾.

斷言6設(shè)dG(v)=7,則

3)v不與(3,3,7)-圈關(guān)聯(lián).

證明令NG(v)={v1,v2,…,v7}.由文獻(xiàn)[15]的斷言6知,1)成立.

3)用反證法.假設(shè)v與(3,3,7)-圈關(guān)聯(lián).設(shè)dG(v1)=dG(v2)=3且v1v2∈E(G).令H=G-v1v2.由注1知,H有一個(gè)T(G)-avd-邊染色φ.設(shè)φ(vvi)=i,i∈[1,7].由注2知,Cφ(v1)=Cφ(v2)={1,2}.用{8,9,10}中的任意一種顏色改染vv1或vv2,得到v的6個(gè)不同的顏色集合.而v至多只有5個(gè)沖突點(diǎn)，所以必存在一種改染方式φ′,使得v不與其鄰點(diǎn)產(chǎn)生沖突且Cφ′(v1)≠Cφ′(v2).由注2知,φ可以擴(kuò)染為G的一個(gè)T(G)-avd-邊染色.矛盾.斷言6證畢.

斷言7設(shè)dG(v)=k且k≥8,則

證明記NG(v)={v1,v2,…,vk}.

2)設(shè)dG(v1)=dG(v2)=3且v1v2∈E(G).令H=G-v1v2,由注1知,H有一個(gè)T(G)-avd-邊染色φ.設(shè)φ(vvi)=i,i∈[1,k].由注2知,Cφ(v1)=Cφ(v2)={1,2}.

3)設(shè)dG(v1)=dG(v2)=4且v1v2∈E(G).令H=G-v1v2,由注1知,H有一個(gè)T(G)-avd-染色φ.設(shè)φ(vvi)=i,i∈[1,k].由注2知,Cφ(v1)=Cφ(v2)={1,2,a}.

令H為G中刪去所有2--點(diǎn)所得到的點(diǎn)數(shù)最多的一個(gè)連通分支,因此,δ(H)≥3且H是無相鄰3-圈的平面圖.根據(jù)斷言1和斷言5～斷言7可推斷出dG(v)和dH(v)的關(guān)系如表1所示.

表1 dG(v)和dH(v)之間的關(guān)系

斷言81)若dH(v)=k且3≤k≤4,則dG(v)=dH(v);

9)任意3-面f至少關(guān)聯(lián)1個(gè)5+-點(diǎn)v.

證明根據(jù)表1和斷言1～斷言3可知,1)～3)和9)顯然是正確的.

下面利用權(quán)轉(zhuǎn)移方法推出矛盾.首先,對(duì)任意x∈V(H)∪F(H),定義初始權(quán)函數(shù)w(x)=dH(x)-4.根據(jù)歐拉公式|V(H)|-|E(H)|+|F(H)|=2,有

下面定義適當(dāng)?shù)臋?quán)轉(zhuǎn)移規(guī)則.在權(quán)轉(zhuǎn)移過程中,總權(quán)和保持不變.記新的權(quán)函數(shù)為w′(x),x∈V(H)∪F(H).若能證明對(duì)任意x∈V(H)∪F(H),有w′(x)≥0,則有如下矛盾:

因此,圖H不存在,從而極小反例圖G不存在,即定理1成立.

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

下面證明對(duì)?v∈V(H),有w′(v)≥0.

設(shè)dH(v)=4.則w′(v)=4-4=0.

因此,完成了定理1的證明.

2 結(jié) 語