雙圈圖的鄰和可區別邊染色

譚鈞銘， 強會英， 劉歡， 王洪申

1.蘭州交通大學 數理學院，蘭州 730070；2.蘭州理工大學 機電工程學院，蘭州 730050

圖G表示一個雙圈圖，圖上的樹的高度稱為雙圈圖的有根樹的高度．樹上最長路的長度，稱為有根樹的高．V(G)，E(G)，Δ(G)分別是圖G的點集合、邊集合、最大度．dG(v)表示在圖G中點v的度，Sφ(v)表示在φ下所有與點v相關聯的邊所染顏色構成的色集合，[k]表示{1，2，…，k}組成的色集合．GΔ表示圖G的全體最大度頂點在圖G中的導出子圖．文中未加說明的符號可參見文獻[9-12]．

1 預備知識

定義2[14]邊數等于頂點數加1的簡單連通圖叫做雙圈圖．

定義3設圖H是無懸掛點的雙圈圖，則H∈{H1，H2，H3，H4，H5}．

圖1 無懸掛點的雙圈圖

2 主要結論

定理1記樹高都為0的雙圈圖分別為H1，H2，H3，H4，H5(如圖1所示)，則

表1 H1的鄰和可區別邊染色

現需證當r，s≡1(mod 3)，t≡0(mod 3)或r，s≡1(mod 3)，t≡2(mod 3)時，H1無3-NSDPEC．

若r?1(mod 3)且s?1(mod 3)．給出H5的一個3-NSDPEC：路xw1…wt-1y依次循環染1，2，3．令ywt-1染a，且{1，2，3}{a}={b，c}．當s≡0(mod 3)時，圈yv1…vs-1y依次循環染c，a，b；當s≡2(mod 3)時，圈yv1…vs-1y依次循環染b，c，a．圈xu1…ur-1x與yv1…vs-1y的染法相似．定理1成立．

將有根樹的樹高大于0且Δ(G)=3的雙圈圖分為3種：α-型雙圈圖，β-型雙圈圖，γ-型雙圈圖．

α-型雙圈圖：設圖G是n階雙圈圖(n≥16)，且同時滿足：(a)Δ(G)=3，GΔ=?；(b) 圖G是在H1的基礎上連接著樹，且在連接(x，y)的3條路中，有任意2條路的路長都恒等于1(mod 3)，另一條路的路長恒等于2(mod 3)；(c) 在路長恒等于2(mod 3)的路中，存在內點z，使得(x，z)與(z，y)的路長均為1(mod 3)；(d) 任意v∈V(H1)z，dG(v)=dH1(v)．

β-型雙圈圖：設圖G是n階雙圈圖(n≥10)，且同時滿足：(a)Δ(G)=3，GΔ=?；(b)G中存在圈C，該圈圈長為r(r≡1(mod 3))，且圈上僅有1個3 度點．

γ-型雙圈圖：除α-型雙圈圖、β-型雙圈圖之外的Δ(G)=3的n階(n≥4)雙圈圖．

情形1 有根樹最大高度為1．

若圖G是α-型雙圈圖．記路P1的長r≡1(mod 3)，路P2的長s≡1(mod 3)，路P3的長t≡2(mod 3)．在表1中r，s≡1(mod 3)，t≡2(mod 3)時4-NSDPEC的基礎上，給出G的一個4-NSDPEC：因GΔ=?，故t≥8．在H1中，點z與其圈上的2個鄰點的色集合分別是{1，2}，{1，3}，{2，3}，則給z的懸掛邊染3即可．

若圖G是β-型雙圈圖．G只能由H5連接懸掛邊所得，且懸掛邊不可能同時在G的2個圈長都恒為1(mod 3)的圈上，也不可能在圈長為3的圈上，有可能在路w2…wt-2(t≥4)上．給G增加懸掛邊，使G的3條路的所有頂點都有懸掛邊(記該圖為G0)．在定理1的H5的4-NSDPEC的基礎上，給出G0的一個4-NSDPEC：路u2…ur-2上的ui(2≤i≤r-2)的懸掛邊染4；路v2…vs-2上的vi(i≡2(mod 3))的懸掛邊染3，其他點的懸掛邊染2；路w2…wt-2上的wi(2≤i≤t-2)的懸掛邊染4．

現在去掉所有添加的懸掛邊，容易得到圖G的一個4-NSDPEC．

情形2 有根樹最大高度大于1．

選樹上具有最大高度的路，其懸掛點為v．v的鄰點w不在圈上，w僅有一個非懸掛鄰點u．反證法：設G是一個極小反例，即G是Δ(G)=3，且使|V(G)|+|E(G)|最小的不存在4-NSDPEC的圖，則G的任意真子圖G′有一個4-NSDPECφ′．令G′=G-wv，下面在G′的基礎上，給邊wv染色，將φ′拓展為G的4-NSDPECφ．

若dG(w)≠dG(u)，則給邊wv正常邊染色就會使w與u鄰點可區別．又因為dG(w)≤3，dG′(w)≤2，故在φ′下，w至少有2色未表現，總有一種色給wv，使得w與u鄰和可區別，得到G的一個4-NSDPEC．與G是極小反例矛盾．

若dG(w)=dG(u)=2，則給邊wv染上G′中點u未表現的色，即可使得w與u鄰和可區別，得到G的一個4-NSDPEC．與G是極小反例矛盾．

綜上所述，定理2成立．

定理3若圖G是γ-型雙圈圖，則

證記圖Gi是在Hi的基礎上連接有根樹得到的雙圈圖，因為Δ(G)=3，故i≠3．

情形1 有根樹最大高度為1．

當G=G1時，根據圖H1的3條路的路長，分以下幾種情況討論：

1) 若H1的3條路的路長是表1中除r，s≡1(mod 3)，t≡0(mod 3)或r，s≡1(mod 3)，t≡2(mod 3)之外的8種情況，則在定理1中H1的3-NSDPEC的基礎上，給G所有懸掛邊正常邊染色，使G中所有3度點的色集合都是{1，2，3}，即得到G的一個3-NSDPEC．

2) 若H1的3條路的路長是r，s≡1(mod 3)，t≡0(mod 3)的情況．圖G的懸掛點可以在P1，P2或P3上．

3)若圖H1的3條路的路長是r，s≡1(mod 3)，t≡2(mod 3)的情況，證明方法與r，s≡1(mod 3)，t≡0(mod 3)的情況類似．

當G=G5時，方法與G=G1時類似．

2) 當H1是r，s≡1(mod 3)，t≡0(mod 3)情況時，給P1上的ur-1的懸掛邊染3，其他點的懸掛邊染4．給P2上的vs-1的懸掛邊染3，點vi(i≡2(mod 3))的懸掛邊染2，其他點的懸掛邊染4．給P3上的wt-1的懸掛邊染3，其他點的懸掛邊染4．

3) 當H1是r，s≡1(mod 3)，t≡2(mod 3)的情況時，給wt-1的懸掛邊染2，vs-1的懸掛邊染1，其他懸掛邊染4．

去掉所有添加的懸掛邊，即得到G1的一個4-NSDPEC．

去掉所有添加的懸掛邊，即得到G2的一個4-NSDPEC．若G=G4或G=G5，染法類似．

選樹上有最大高度的路，其懸掛點為v．v的鄰點w不在圈上，w僅有一個非懸掛鄰點u．令G′=G-wv，下面在G′的基礎上，給wv染色，將φ′拓展為G的s-NSDPECφ．

當dG(w)≠dG(u)時，若dG(w)=3，則給wv正常邊染色，必有fφ(w)≠fφ(u)；若dG(w)=2，則dG′(w)=1，在G′中w有2色未表現，故總有1色給wv，使得fφ(w)≠fφ(u)，從而得到圖G的一個3-NSDPEC．與G是最小反例矛盾．

當dG(w)=dG(u)時，給wv染上u未在G′表現的色，即得到G的一個3-NSDPEC．與G是最小反例矛盾．

當dG(w)≠dG(u)時，因dG(w)≤3，dG′(w)≤2，則在G′中w至少有2色未表現，則總有1色給wv，使得fφ(w)≠fφ(u)，從而得到G的一個4-NSDPEC．與G是最小反例矛盾．

當dG(w)=dG(u)，且φ′的點w表現的色都在u上表現時，則給wv染上u未在G′中表現的色，即可得到圖G的一個4-NSDPEC．與G是最小反例矛盾．

當dG(w)=dG(u)，且φ′的點w表現的某色沒在u上表現時，由于dG(w)≤3，dG′(w)≤2，則在G′中w至少有2色未表現，總有1色給wv，使得fφ(w)≠fφ(u)，從而得到G的一個4-NSDPEC．與G是最小反例矛盾．

綜上所述，定理3成立．

定理4若圖G是Δ(G)≥4的，且有根樹最大高度大于0的雙圈圖，則

證記圖Gi是在Hi(1≤i≤5)的基礎上連接有根樹得到的雙圈圖．

情形1 若有根樹的最大高度為1，則根據有根樹的位置和圈上相鄰點的度分3種情況討論．

情形1.1 圖H上所有2度點z在圖G中的度也為2，即dH(z)=dG(z)=2．則懸掛邊只能在x或y處．不妨設dG(x)=k，dG(y)=l，且k≥l≥1．

又因為k≥l≥1，故dG(x)=Δ(G)，則對點x的所有懸掛邊正常邊染色就能使得點x與x的鄰點鄰和可區別，即得到圖G的一個Δ(G)-NSDPEC．

當G=Gi(2≤i≤5)時，方法與G=G1類似．

情形1.2 圖H上存在2度點z，使得dH(z)=2且dG(z)≥3，且對任意滿足該條件的點z，有dG(z)=dG(z′)=dG(z″)．其中z′，z″是z在H上的2個鄰點．

圖2 滿足情形1.2與情形1.3(2)的雙圈圖的基本結構

令G′=G-zz1-zz2，對zz1，zz2重新染色x1，x2．f′(z)表示在G′中z的色集合的所有元素的加和．邊zz1，zz2可用顏色集分別為S1，S2，由正常邊染色的條件得

|S1|=|S2|=(Δ(G)+1)-(Δ(G)-2)=3

再由鄰和可區別邊染色的條件得

Q(x1，x2)=(x1-x2)(x1+x2+f′(z)-f(z′))(x1+x2+f′(z)-f(z″))

情形1.3 圖H上存在一個2度點z，使得dH(z)=2且dG(z)≥3，且dG(z)≠dG(z′)．其中z′，z″是點z在H上的2個鄰點．

1) 當H=H3，Δ(G)=4，且x是G的唯一最大度點時．令G′=G-zv，zv是懸掛邊．因3度點z與其鄰點僅有1+2+3=2+4，1+2+4=3+4鄰和相等的情況．故z與z′，z″的公共邊染2，4，導致z最多與一個2度點鄰和相等．在G′的4-NSDPEC的基礎上，zv有2色未表現，則總存在1色給zv，得到G的一個4-NSDPEC．與G是最小反例矛盾．

2) 其他情況時，令G的最大度點為u，uv是懸掛邊．令G′=G-uv，對uv正常邊染色即得到G的一個Δ(G)-NSDPEC．與G是最小反例矛盾．

令G′=G-uu1，則對uu1重新染色x1．記uu1可用顏色集為S1．由正常邊染色的條件得

|S1|=(Δ(G)+1)-(dG(u)-1)≥(Δ(G)+1)-(Δ(G)-2)=3

再由鄰和可區別邊染色的條件得

Q(x1)=(x1+f′(u)-f(u′))(x1+f′(u)-f(u″))

情形2 有根樹的最大高度大于1．

選樹上具有最大高度的路，其懸掛點為v．點v的鄰點w不在圈上，且w僅有1個非懸掛鄰點u．令G′=G-wv，下面在G′的基礎上，給邊wv染色，將φ′拓展為G的s-NSDPECφ．

當dG(w)≠dG(u)時，給wv正常邊染色可使Sφ(w)≠Sφ(u)．故給wv染色時，只需考慮fφ(w)與fφ(u)是否相等．若dG(w)=Δ(G)，給wv正常邊染色，必有fφ(w)≠fφ(u)；若dG(w)≤Δ(G)-1，則dG′(w)≤Δ(G)-2，即在G′中w至少有2色未表現，且最多有1色給wv，使得fφ(w)=fφ(u)．故總有1色給wv，使得w與u鄰和可區別，從而得到G的一個Δ(G)-NSDPEC．與G是最小反例矛盾．

當dG(w)=dG(u)，且φ′的點w表現的色都在u上表現時，給邊wv染上點u未在φ′中表現的色，即可得到圖G的一個Δ(G)-NSDPEC．與G是最小反例矛盾．

當dG(w)=dG(u)，且φ′的點w表現的某色未在u上表現時，由于dG(w)≤Δ(G)-1，則dG′(w)≤Δ(G)-2，即在G′中w至少有2色未表現，且最多有1色給wv，使得fφ(w)=fφ(u)．故總有1色給wv，使得w與u鄰和可區別，從而得到G的一個Δ(G)-NSDPEC．與G是最小反例矛盾．

綜上所述，定理4成立．