稀疏圖的局部嚴(yán)格鄰點可區(qū)別邊染色

中圖分類號：0157.5 文獻(xiàn)標(biāo)志碼：A 文章編號：1671-5489（2025）04-1083-08

Local Strict Neighbor-Distinguishing Edge Coloring of Sparse Graphs

PENG Yan，CHEN Lili （School of Mathematical Sciences， Huaqiao University，Quanzhou 362O21， Fujian Province ，China）

Abstract：By using the discharging method，we study the local strict neighbor-distinguishing edge coloring problem of sparse graphs，and obtain that if G is a graph with maximum degree at most four and maximum average degree mad（G）lt;31， ，thenthelocalstrictneighbor-distinguishingindexofG is at most 10.

Keywords： sparse graph； local strict neighbor-distinguishing edge coloring;； maximum average degree; discharging method

引言與主要結(jié)果

本文考慮有限無向簡單連通圖．對于簡單圖 G ，用 V（G） 和 E（G） 分別表示 G 的頂點集和邊集，|V（G）| 和 ∣E（G） 分別表示 G 的頂點數(shù)和邊數(shù)．對任一頂點 Π_v∈V（G） ，與 υ 關(guān)聯(lián)的邊數(shù)稱為 υ 在 G 中的度，記為 d_G（v） ．若" ，則 v 稱為 點．若 ，則 v 稱為 k^- 點．若 u 為 v 的鄰點，且d_G（u）=k ，則 u 稱為 v 的 k^- 鄰點．記 Δ（G） 和 δ（G） 分別表示圖 G 的最大度和最小度．在不引起混淆的情況下，將 Δ（G） 簡寫為 圖 G 的最大平均度定義為 若 G 不含1度點，則稱 G 是正規(guī)圖.

圖 G 的一個正常 k^- 邊染色是一個映射 ，使得對任意相鄰的頂點 u 和 ? ，有φ（u）≠φ（v） ．給定圖 G 的一個正常 k^- 邊染色 φ ，用 S_φ（υ） 表示與 v 相關(guān)聯(lián)的邊的顏色集合．在不引起混淆的情況下，將 S_φ（υ） 簡記為 S（σ） ．設(shè) φ 是圖 G 的一個正常 k^- 邊染色．若 φ 滿足對任意相鄰的頂點u 和 v ，有 且 ，則稱 φ 是嚴(yán)格鄰點可區(qū)別的．使得 G 有一個嚴(yán)格鄰點可區(qū)別k^- 邊染色的最小整數(shù) k 稱為 G 的嚴(yán)格鄰點可區(qū)別邊色數(shù)，記為 χ_snd^′（G） ．易見， G 有嚴(yán)格鄰點可區(qū)別邊

染色當(dāng)且僅當(dāng) G 是正規(guī)圖.

嚴(yán)格鄰點可區(qū)別邊染色的概念由 Gu 等[1]于2021年提出，同年，Przybylo等[2]也提出了相同的概念，命名為 inclusion-free 邊染色．實際上，Zhang[3]在 2008年就提出了該概念，將其命名為Smarandachely鄰點邊染色，并提出如下猜想.

猜想 1^[3] （204號 對每個連通正規(guī)圖 G ，如果 G≠C₅ ，則 χ_snd^′（G）?2Δ

Gu 等[1]證明了存在 H_k 這類圖不滿足猜想1，其中 H_k 為由二部圖 K_2，k 的一條邊插入一個2度點得到的圖．于是，他們對猜想1做了修改：

猜想 2^[1] （204號 對每個連通正規(guī)圖 G ，如果 G≠H_k ，則 χ_snd^′（G）?2Δ

對于一般正規(guī)圖，王鴻杰等[4給出了嚴(yán)格鄰點可區(qū)別邊色數(shù)的一個較大上界，即 20Δ²-28Δ+12 劉信生等[5-6]先證明了對每個最大度 Δ?16 的連通正規(guī)圖，都有 ，又進(jìn)一步證明了存在一個常數(shù) c ，使得對每個滿足最大度 Δ?10²⁰ 且圍長 的正規(guī)圖 G ，有（20 χ_snd^′（G）?Δ+301 ．Przybylo等[2]與井普寧等[改進(jìn)了文獻(xiàn)[4]的結(jié)果，分別證明了對每個正規(guī)圖 G 有χ_snd^′（G）?3Δ-1 ，

對于特殊圖類， Gu 等[1]和Chen等[8]分別證明了對每個次立方圖 G ， χ_snd^′（G）?7 ，且 χ_snd^′（G）=7 當(dāng)且僅當(dāng) G 同構(gòu)于 H₃ ： Gu 等[9證明了最小度至少為2的 K₄ -minor-free圖的嚴(yán)格鄰點可區(qū)別邊色數(shù)至多為 2Δ+1 ，且嚴(yán)格鄰點可區(qū)別邊色數(shù)達(dá)到 2Δ+1 當(dāng)且僅當(dāng)圖 G 為 H_Δ ．對于二部圖，Chen等[10]證明了對于 （2，Δ） -二部圖 G ，有 χ_snd^′（G）?2Δ ；對任意 δ（H）≥2 的 （3，Δ）- 二部圖 H ，有 χ_snd^′（H）?2Δ+1 彭燕等[]證明了最大度為 的Halin圖 G ，其嚴(yán)格鄰點可區(qū)別邊色數(shù) χ_snd^′（G）?Δ+2.Huang 等[12-13]給出了一類三正則Halin圖以及最大度至少為4的Halin圖的嚴(yán)格鄰點可區(qū)別邊色數(shù)的精確值.

井普寧等[7在研究平面圖的嚴(yán)格鄰點可區(qū)別邊染色時引人了嚴(yán)格鄰點可區(qū)別邊染色的松弛形式，即局部嚴(yán)格鄰點可區(qū)別邊染色．對于一般圖 G （不一定是正規(guī)圖），設(shè) φ 是圖 G 的一個正常 k^- 邊染色.若對任意相鄰的 點 u 和 υ ，有 且 （此時稱 u 和 υ 互斥），則稱 φ 是 G 的局部嚴(yán)格鄰點可區(qū)別邊染色．使得 G 有局部嚴(yán)格鄰點可區(qū)別邊染色所需的最小顏色數(shù)稱為 G 的局部嚴(yán)格鄰點可區(qū)別邊色數(shù)，記為 χ_lnd^′（G） ．顯然，若 G 是一個正規(guī)圖，則 χ_lnd^′（G）=χ_snd^′（G）

井普寧等[證明了：每個 Δ?2 的圖 G ，均有 χ_lnd^′（G）?3Δ=1 ；對于圍長至少為5的平面圖 G ，有χ_ind^′（G）?Δ+25 ．Wang等[14]證明了：對任意的平面圖 G ， χ_lnd^′（G）??2.8Δ?+4 ；當(dāng) G 是不含4-圈的平面圖時， χ_lnd^′（G）?2Δ+10 ；當(dāng) G 是3-連通的平面圖時， χ_lnd^′（G）?Δ+23 ；當(dāng) G 是Hamilton 平面圖時， χ_lnd^′（G）?Δ+6.

本文研究最大度 Δ?4 的簡單連通圖 G 的局部嚴(yán)格鄰點可區(qū)別邊染色，得到如下結(jié)果.

定理1設(shè)圖 G 的最大度 Δ?4 且最大平均度 ，則 χ_lnd^′（G）?10 由于當(dāng) G 是正規(guī)圖時 ，因此有如下推論.

推論1設(shè)圖 G 是正規(guī)圖，最大度 Δ?4 且最大平均度 ，則 χ_snd^′（G）?10

2 定理1的證明

假設(shè)圖 G 是定理1的反例且 |E（G）| 盡可能小，即 G 的最大度 Δ?4 ，最大平均度 且 χ_lnd^′（G）?11 ．但對任意 |E（G^′）|lt;|E（G）| 的圖 G^′ 有 若 φ 是 G^′ 的一個局部嚴(yán)格鄰點可區(qū)別邊染色，且 χ_lnd^′（G^′）?10 ，則稱 φ 是 G^′ 的一個好的染色．本文的目標(biāo)是把 φ 拓展成 G 的一個好的染色，從而與 G 的選擇矛盾.

令 C={1，2，…，10} 表示染色所用的顏色集合．設(shè) φ 是 G^′ 的一個好的染色．對于邊 ，用 A（uv） 表示邊 uv 可用的顏色集合．在給邊 uv 進(jìn)行染色時，從頂點 u 來看，首先， uv 不可以染 S_φ（u） 中的任何顏色，否則與正常邊染色矛盾；其次，設(shè) u^' 為 u 除 υ 外的一個鄰點，若對 uv 染顏色 會使得 S_φ^'（u）?S_φ^'（u^′） 或 S_φ^'（u^′）?S_φ^'（u） ，則 uv 不可染顏色 α ，其中φ^′ 為染完邊 uv 后的染色．記 R（u） 為所有這樣的 α 構(gòu)成的集合．將 S_φ（u）?R（u） 稱為邊 uv 關(guān)于頂點 u （204號的禁用色集，記為 F（uv，u） ．根據(jù)定義，當(dāng) uv 不染 F（uv，u） 中顏色時， u 和 u 的鄰點（ υ 除外）是互斥的．同理可得邊 uv 關(guān)于頂點 v 的禁用色集 F（uv，v） ．從而邊 uv 可用的顏色集合 ?F（uv，v））

2.1 預(yù)備引理

引理1設(shè) φ 是 G 的一個正常邊染色， v₁v₂∈E（G） ．若 2?d_G（v₁）?d_G（v₂） ，且存在顏色 ，則 v₁ 與 σ_v2 互斥.

證明：由 2?d_G（v₁）?d_G（v₂） ，有 |S（v₁）|?|S（v₂）| .若 ，則 S（v₂）?S（v₁） ，即|S（v₂）|?|S（v₁）| .又 ，則有 |S（v₂）|lt;|S（v₁）| ，與 |S（v₁）|?|S（v₂）| 矛盾．因而 ，即 結(jié)合 ，即 ，所以 v₁ 與 σ_v2 （20互斥．證畢.

對于邊 uv 關(guān)于頂點 u 的禁用色集 F（uv，u） ，有如下性質(zhì).

引理2設(shè) G^′?G ， φ 是 G^′ 的一個好的染色．令邊 ，則下列結(jié)論成立：

1）若 d_G^'（u）=1 ，則 ∣F（uv，u）∣=d_G^'（u₁）?4 ，其中 u₁ 為 u 在 G^′ 中的鄰點；

2）若 d_G^'（u）=2 ，則 ∣F（uv，u）∣=2+d_u²?4 ，其中 d_u²=|{w|uw∈E（G^′） 且 d_G^'（τν）=2}| ：

3）若 d_G^'（u）=3 ，則 ，其中 d_u³=∣{w∣uw∈E（G^′） 且 2?d_G^′（w）?3}∣ ：

證明：由于 Δ（G）?4 ，因此 0?d_G^′（u）?3

若 d_G^'（u）=0 ，則 ∣F（uv，u）∣=? 若 d_G^'（u）=1 ，則 d_G（u）=2 設(shè) u₁ 為 u 在 G^′ 中的鄰點．此時S_φ（u）?R（u） 為 u₁ 關(guān)聯(lián)的所有邊的顏色，即 F（uv，u）=S_φ（u₁） ．所以 ∣F（uv，u）∣=d_G^'（u₁）?4

若 d_G^'（u）=2 ，則 d_G（u）=3 設(shè) u₁?u₂ 為 u 在 G^′ 中的鄰點．對于 1?i?2 ，若 d_G^'（u_i）=2 ，設(shè) u_i^' 為u_i 在 G 中除 u 外的另一個鄰點，則 φ（u_iu_i^′）∈R（u） .若 d_G^'（u_i）{?3 ，不妨設(shè) d_G^'（u₁）≥3 ．由于在 φ 下 u 與 u₁ 互斥，故有 ．此時，對 uv 染 中的任一顏色，得到的染色是正常染色，且由于 d_G（u）?d_G（u₁） ，根據(jù)引理1知，在新的染色下仍有 u 與 u₁ 互斥．所以當(dāng) d_G^'（u_i）{?3 時， 中的顏色均不是 uv 的禁用色．綜上， |R（u）| 為 u 在 G^′ 中的2-鄰點的個數(shù)．令 d_u²= |{τυ|uτυ∈E（G^′） 且 d_G^'（τυ）=2}| ，則有 |F（uv，u）|=∣S_φ（u）∣+∣R（u）∣=2+d_u²?4.

最后假設(shè) d_G^'（u）=3 ．對于 1?i?3 ，設(shè) u_i 為 u 在 G^′ 中的鄰點．若 d_G^'（u_i）=2 ，則顯然有 .若 d_G^'（u_i）=3 ，記 u_i^'，u_i^′′ 為 u_i 除 u 外的鄰點．若 φ（u_iu_i^'） 和 φ（u_iu_i^′′） 有一個在S_φ（u） 中，不妨設(shè) φ（u_iu_i^′）∈S_φ（u） ，則 uv 染 φ（u_iu_i^′′） 會導(dǎo)致 S_φ^'（u_i）?S_φ^'（u） ，其中 φ^' 為染完邊 uv 后的染色，從而 φ（u_iu_i^′′）∈R（u） .若 φ（u_iu_i^′） 和 φ（u_iu_i^′′） 均不在 S_φ（u） 中，則 中的顏色均不是uv 的禁用色．若 d_G^'（u_i）=4 ，則由于在 φ 下， 且 d_G（u）?d_G（u_i） ，由引理1知，對uv 染 中的任意一種顏色仍有 u 與 u_i 互斥．因此， 中的顏色不是 uv 的禁用色.綜上，只有 u_i 為2-點或3-點時， S_φ（u_i）?S_φ（u） 中可能存在一種顏色屬于 R（u） ．因此，令 且 ，則有 |F（uv，u）|=|S_φ（u）|+|R（u）|?3+d_u³?6. ，證畢.

2.2 圖 的結(jié)構(gòu)性質(zhì)

下面給出極小反例圖 G 的一些結(jié)構(gòu)性質(zhì)．令 C={1，2，…，10} 表示染色所用的顏色集合.

引理3 δ（G）≥2

證明：設(shè) _v∈V（G） 且 ， u 是 v 的鄰點．令 G^′=G-v ，則 |E（G^′）|lt;|E（G）| ，由 G 的極小性知， G^′ 有一個好的染色 φ 、易知 ．由引理2知， ∣F（uv，u）∣?6 ，所以 |A（uv）|?4 因此可將 uv 染 A（uv） 中的顏色，從而得到 G 的一個好的染色，與 G 是極小反例矛盾．證畢.

引理42-點與2-點不相鄰.

證明：設(shè) v₁，v₂∈V（G） ， v₁v₂∈E（G） 且 d_G（v₁）=d_G（v₂）=2 令 v₁^′ 是 除 v₂ 外的另一個鄰點，v₂^′ 是 σ_v2 除 v₁ 外的另一個鄰點．令 G^′=G-v₁ ，則 |E（G^′）|lt;|E（G）| ，因而 G^′ 有一個好的染色 φ

令 由于 d_G^'（v₁^'）?3 ，

d_G^'（v₂）=1 ，由引理2知， ∣F（v₁v₁^′，v₁^′）∣?6 ， ，從而

所以 a 和 b 存在．將邊 v₁v₁^′ 染 α_a ，邊 v₁v₂ 染 b ．不難驗證，在新的染色下， 與 v₁^′ 互斥， v₁ 與 σ_v2 互斥， v₁^′ 與其鄰點互斥， v₂ 與 v₂^′ 互斥．因此該染色是 G 的一個好的染色，與 G 是極小反例矛盾．證畢.

引理5 2-點與3-點不相鄰.

證明：設(shè) v₁，v₂∈V（G） ， v₁v₂∈E（G） ，且 d_G（v₁）=2 ， d_G（v₂）=3 .令 v₁^′ 是 v₁ 除 σ_v2 外的另一個鄰點， u₁?u₂ 是 v₂ 除 外的另兩個鄰點．令 G^′=G-v₁ ，則 G^′ 有一個好的染色 φ

令 ．由于d_G^'（v₁^'）?3 ， d_G^'（v₂）=2 ，因此由引理2知，有 ∣F（v₁v₁^′，v₁^′）∣?6 ， ，從而

所以 a 和 b 存在．將邊 v₁v₁^′ 染 Δ_a ，邊 v₁v₂ 染 b ．不難驗證，在新的染色下， 與 v₁^′ 互斥， v₁ 與 σ_v2 互斥， v₁^′ 與其鄰點互斥， σ_v2 與其鄰點互斥．因此該染色是 G 的一個好的染色，與 G 是極小反例矛盾.證畢.

引理6 3-點與3-點不相鄰.

證明：設(shè) v₁，v₂∈V（G） ， v₁v₂∈E（G） ，且 d_G（v₁）=d_G（v₂）=3 令 u₁，u₂ 是 v₁ 除 σ_v2 外的另兩個鄰點， 是 v₂ 除 v₁ 外的另兩個鄰點．由引理3和引理5知，對 1?i?2 ，有 d_G（u_i）?3 ， d_G（τ_i）≥3 令 G^′=G-v₁ ，則 G^′ 有一個好的染色 φ

首先，令 ．由引理2知， ∣F（v₁u₁，u₁）∣?6 ，因此

所以 Δ_a 存在，將邊 v₁u₁ 染 α_a

其次，令 ．由引理2知， ∣F（v₁u₂，u₂）∣?6 ，因此

所以 b 存在，將邊 v₁u₂ 染 b

最后，令 ．由于 d_G^'（v₂）=2 ，且 d_G（w₁）?3 ， d_G（w₂）?3 ，因此由引理2中2）知，有 d_v2²=0 ，從而 $＼big | F （ v _ { 1 } v _ { 2 } ， v _ { 2 } ） ＼big | ＼bigleqslant 2$ ，故

所以 c 存在，將邊 v₁v₂ 染 c

記新的染色為 φ^' ，易見在 φ^' 下， .又由于 d_G（v₁）?d_G（u₂） ， d_G（v₁）?d_G（u₁） ， d_G（v₁）=d_G（v₂） ，由引理1知， v₁ 與 u₂ 互斥， v₁ 與 u₁ 互斥，v₁ 與 σ_v2 互斥．因此該染色是 G 的一個好的染色，與 G 是極小反例矛盾．證畢.

引理74-點至多存在兩個2-鄰點.

證明：設(shè) v∈V（G） ，且 .令 v₁，v₂∈?₃，v₄ 為 υ 的鄰點，且 v₁?v₂?v₃ 為2-點．由引理4知，對任意 i，j∈{1，2，3} ， i≠j ，有 σ_vi 與 ?_Vj 不相鄰．對于 1?i?3 ，設(shè) u_i 為 v_i 除 v 外的另一個鄰點，由引理 3～ 引理5可知， d_G（u_i）=4 ．下面分3種情形證明 G 有一個好的染色.

情形1） u₁=u₂=u₃ ：

記 u₁?u₂?u₃ 為 u ，設(shè) u 除 外的鄰點為 w 令 G^′=G-v₁ ，則 G^′ 有一個好的染色 φ .令 由于 d_G^'（u）=d_G^'（v）=3 ，由引理2中3）知， |F（v₁u，u）|?6 ， ∣F（vv₁，v）∣?6 ，且 {φ（vv₂），φ（vv₃）}?F（v₁u，u） ， {φ（v₂u） ， φ（v₃u）}? F（vv₁，v） ．所以

因為

所以 a 和 b 存在．將邊 v₁u 染 a ，邊 vv₁ 染 b ．不難驗證，該染色是 G 的一個好的染色.

情形2） u₁?u₂?u₃ 中有兩個頂點相同.

不妨設(shè) u₁=u₂ .記 u₁，u₂ 為 u ，設(shè) u 除 σ_v1，v₂ 外的另兩個鄰點為 .令 G^′=G-v₁ ，則 G^′ 有一個好的染色 φ .令 ， .由于 d_G^'（u）= d_G^'（v）=3 ，由引理2中3）知， ∣F（v₁u，u）∣?6 ， ∣F（vv₁，v）∣?6 ，且 φ（vv₂）∈F（v₁u，u） ， φ（v₂u）∈ F（vv₁，v） ．所以

F（v₁u，u）?S_φ（v）=F（v₁u，u）?{φ（vv₃），φ（vv₄）}，

F（vv₁，v）?S_φ（u）?{a}=F（vv₁，v）?{φ（uw₁），φ（uw₂），a}.

因為

所以 a 和 b 存在．將邊 v₁u 染 a ，邊 vv₁ 染 b ．不難驗證，該染色是 G 的一個好的染色.

情形3） 為兩兩不同的頂點.

令 G^′=G-{v，v₁，v₂，v₃} ，則 G^′ 有一個好的染色 φ

先對邊 v₁u₁，v₂u₂，v₃u₃ 進(jìn)行染色．由于 υ 關(guān)聯(lián)的邊還未染色，因此對于 1?i?3 ， A（v_iu_i）= .由于 d_G^'（u_i）=3 ，由引理2中3）知， ∣F（v_iu_i，u_i）∣?6 ，因此 ∣A（v_iu_i）∣?10-6=4 又因為 ，所以存在 i，j∈{1，2，3} ， i≠j ，使得 A（v_iu_i）? A（v_ju_j）≠0 ．不妨設(shè) A（v₁u₁）?A（v₂u₂）≠? ，令 a∈A（v₁u₁）?A（v₂u₂） ，并用 a 給邊 v₁u₁，v₂u₂ 染色，再取 給邊 v₃u₃ 染色.

下面依次對邊 vv₄ v₄，vv₁，vv₂，vv₃ 進(jìn)行染色．先考慮邊 vv₄ .令 ．由于d_G^'（v₄）?3 ，由引理2知， ∣F（vv₄，v₄）∣?6 ，所以 Ψ_c 存在，將邊 vv₄ 染 Ψ_c ．對于邊 vv₁ ，若 v₄ 為2-點，則令 ，否則，令 ．因為 |S_φ（u₁）|=3 ，且 v₄ 為2-點時 ，所以 d 存在，將邊 vv₁ 染 d ．對于邊 vv₂ ，若 v₄ 為2-點，設(shè) u₄ 為 v₄ 除 υ 外的鄰點，令 .若 v₄ 為3-點，則當(dāng) d∈S_φ（v₄） 時，顏色 g0gggggg 是 vv₂ 的禁用色，此時令 ；否則，令 ．若v₄ 為4-點，令 .由于 ∣S_φ（u₂）∣=3 ，所以 e 存在，將邊 vv₂ 染 Ψ_e ．最后考慮邊 vv₃ .若 v₄ 為2-點，設(shè) u₄ 為 σ_v4 除 υ 外的鄰點，令 .若 v₄ 為3-點，當(dāng) S_φ（v₄） 含有顏色 d 或 e 時，存在顏色 γ∈S_φ（v₄） 是 vv₃ 的禁用色，此時令 {a，b，c，d，e，γ}） ；否則，令 .若 v₄ 為4-點，當(dāng) {d，e}?S_φ（v₄） 時，存在顏色 ζ∈S_φ（v₄） 是 vv₃ 的禁用色，此時令 ；否則，令 {a，b，c，d，e}） .由于 ，所以 f 存在，將邊 vv₃ 染 f ．不難驗證該染色是 G 的一個好的染色.

綜上可見，上述3種情形均可得到 G 的一個好的染色，與 G 是極小反例矛盾．證畢.

引理8 4-點至多存在兩個3-鄰點.

證明：設(shè) Π_v∈V（G） ，且 .令 v₁，v₂，v₃，v₄ 為 v 的鄰點，且 d_G（v₁）=d_G（v₂）=d_G（v₃）=3 由引理6知， v₁?v₂?v₃ 互不相鄰．由引理3知， d_G（v₄）≥2 ，由引理3、引理5和引理6可知， v₁?v₂?v₃ （204號在 G 中的鄰點均為4-點.

令 G^′=G-v ，則 G^′ 有一個好的染色 φ ，且 |S_φ（v₁）|=|S_φ（v₂）|=|S_φ（v₃）|=2 .對于 1?i?3 ，由于 d_G^'（v_i）=2 ，且 v_i 除 υ 外的其余鄰點度數(shù)為4．由引理2中2）知， d_vi²=0 ，從而

下面依次對邊 進(jìn)行染色，根據(jù) d_G（v₄） 的值分3種情形討論.

情形1） d_G（v₄）=2

令 JS_φ（v₄）∪{a} ，

由于 d_G^'（v₄）=1 ，由引理2中1）知， ∣F（vv₄，v₄）∣?4. ，又因為 |S_φ（v₁）|=|S_φ（v₂）|=|S_φ（v₃）|=2 ∣S_φ（v₄）∣=1 ，且當(dāng) 1?i?3 時， ∣F（vv_i，v_i）∣?2 ，而 |C|=10 ，因此 均存在．將邊 vv₁ 染 Ω_a ，邊 vv₂ 染 b ，邊 vv₃ 染 c ，邊 vv₄ 染 d ，得到的染色記為 φ^' ．此時， S_φ^'（v）={a，b，c，d} ．易見 S_φ^'（υ₁） 中含顏色 Ψ_a ，但不含顏色 ^b，c ，因此 ，而 |S_φ^'（υ₁）|=3 ，所以 又因為 ，所以 υ 與 v₁ 互斥．同理， S_φ^'（υ₂） 中含顏色 b ，但不含顏色 a，c ， S_φ^'（υ₃） 中含顏色 Ψ_c ，但不含顏色 α_a，b ，所以 v 與 v₂ 互斥， v 與 v₃ 互斥．又由于 S_φ^'（υ₄） 中不含顏色 ω_a，b，c ，因此 υ 與v₄ 互斥．易驗證 φ^' 是 G 的一個好的染色.

情形2） d_G（v₄）=3

令a∈C＼（ （S_φ（v₄）∪{a}? 此時，|S_φ（v₁）|=|S_φ（v₂）|=|S_φ（v₃）|=|S_φ（v₄）|=2 ，由于 d_G（v₄）=2 ，由引理2中2）知， |F（vv₄，v₄）|?4 且對于 1?i?3 ， ∣F（vv_i，v_i）∣?2 ，而 |C|=10 ，因此 均存在．將邊 vv₁ 染 α_a ，邊 vv₂ 染 b ，邊vv₃ 染 c ，邊 vv₄ 染 d ，得到的染色記為 φ^' ．此時， S_φ^'（v）={a，b，c，d} .由于 中含顏色 α_a ，但不含顏色 b，c ： S_φ^'（υ₂） 中含顏色 b ，但不含顏色 a，c;S_φ^'（v₃） 中含顏色 c ，但不含顏色 ψ_a，b S_φ^'（υ₄） 中含顏色d ，但不含顏色 ψ_a，b ，所以 υ 與 v₁，v₂，v₃ 和 v₄ 均是互斥的．易驗證 φ^' 是 G 的一個好的染色.

情形3） d_G（v₄）=4

令 ）U{a}）， ．此時， ∣S_φ（v₁）∣= ∣S_φ（v₂）∣=∣S_φ（v₃）∣=2 ， ∣S_φ（v₄）∣=3 .由于 d_G^'（v₄）=3 ，由引理2中3）知， ∣F（vv₄，v₄）∣?6 ，且對于 1?i?3 ， ∣F（vv_i，v_i）∣?2 ，而 |C|=10 ，因此 a，b，c，d 均存在．將邊 vv₁ 染 Ψ_a ，邊 vv₂ 染 b ，邊 vv₃ 染c ，邊 vv₄ 染 d ，得到的染色記為 φ^' ．此時， S_φ^′（v）={a，b，c，d} ．由于 S_φ^'（υ₁） 中含顏色 α_a ，但不含顏色^b，c ： S_φ^'（υ₂） 中含顏色 b ，但不含顏色a，c； S_φ^'（v₃） 中含顏色 Ψ_c ，但不含顏色 α_a，β_b ．所以 υ 與 σ_v1，v₂ 和 σ_v3 均是互斥的．又 S_φ^'（v₄） 中不含顏色 α_a ，但 S_φ^′（v） 中含顏色 α_a ，且 ∣S_φ^′（v₄）∣=∣S_φ^′（v）∣ ，所以 υ 與 v₄ 均互斥．易驗證 φ^' 是 G 的一個好的染色.

綜上可見，上述3種情形均可得到 G 的一個好的染色，與 G 是極小反例矛盾．證畢.

引理9若4-點有2-鄰點，則其無3-鄰點.

證明：設(shè) υ∈V（G） ，且 $d _ { G } （ ＼ b { ＼mathscr { v } } ） = 4$ .令 v₁，v₂，v₃，v₄ 為 υ 的鄰點，且 d_G（v₁）=2 ， d_G（v₂）=3 .令 w 為log₁ 除 v 外的另一個鄰點，由引理 3～ 引理6可知 d_G（τ）=4 ，由引理5知， v₁ 與 v₂ 不相鄰．易知， γ_v3，v₄ （20號可能為2-點、3-點、4-點.

當(dāng) υ 有4-鄰點時，不妨設(shè) σ_v3 為4-點．令 G^′=G-v₁ ，則 G^′ 有一個好的染色 φ ，且 |S_φ（v）|= ∣S_φ（τυ）∣=3 .令 ， ．由于 d_G^'（τv）= ，但 d_G^'（v₃）=4 ，由引理2中3）知， d_v²?2 ，從而 |F（v₁w，w）|?6 ， |F（v₁v，v）|?3+d_v²?5 所以 ψ_a，b 存在，將邊 v₁w 染 a ，邊 vv₁ 染 b ．不難驗證，該染色是 G 的一個好的染色.

當(dāng) v 無4-鄰點時，由引理7和引理8知， v₃?v₄ 中一個是3-點、一個是2-點，不妨設(shè) σ_v3 為3-點，v₄ 為2-點．由引理 3～ 引理6知， Δ_v3Δ，v₄ 的鄰點均為4-點．令 G^′=G-v ，則 G^′ 有一個好的染色 φ .令a 2）U{a}）， c∈ ·由于 d_G^'（v₁）=d_G^'（v₄）=1 ，因此由引理2中1）知， ∣F（vv₁，v₁）∣?4 ， ∣F（vv₄，v₄）∣?4 ．對于 i∈ {2，3} ，由于 d_G^'（v_i）=2 ，且 v_i 除 v 外的其余鄰點均為4-點，因此 d_vi²=0 ，由引理2中2）知，∣F（vv_i，v_i）∣?2 ，又因為 |S_φ（v₁）∣=∣S_φ（v₄）∣=1 ， ∣S_φ（v₂）∣=∣S_φ（v₃）∣=2 ，而 |C|=10 ，因此 α_a，b c，d 均存在．將邊 vv₁ 染 α_a ，邊 vv₄ 染 b ，邊 vv₂ 染 Ψ_c ，邊 vv₃ 染 d ，得到的染色記為 φ^' ．此時 S_φ^'（v）= {a，b，c，d} .由于 S_φ^'（υ₂） 中含顏色 Ψ_c ，但不含顏色a，b， S_φ^'（v₃） 中含顏色 d ，但不含顏色 a，c ，所以 υ 與v₂ 和 σ_v3 互斥．對于頂點 v₁，v₄，S_φ^'（v₁）∩S_φ^'（v）={a} ， S_φ^′（v₄）?S_φ^′（v）={b} ，而 |S_φ^'（v₁）|= ， ∣S_φ^'（v）∣=4 ，所以 υ 與 v₁ 和 v₄ 互斥．因此該染色是 G 的一個好的染色.

上述兩種情形均可得到 G 的一個好的染色，與 G 是極小反例矛盾．證畢.

記有 i 個2-鄰點的4-點為 4_i- 點，其中 i∈{1，2} ．由引理 3～ 引理5可知，2-點的鄰點均為4-點.下面分析2-點的鄰點的結(jié)構(gòu)性質(zhì).

引理102-點的兩個4-鄰點至少有一個是 4₁? 點.

證明：設(shè) v∈V（G） 且 d_G（v）=2 .令 為 v 的鄰點，且 d_G（u）=d_G（w）=4 令 為 u 除 υ 外的其余3個鄰點， τ_w1，τ_w2，τ_w3 為 w 除 v 外的其余3個鄰點．設(shè) 均不是 4₁ -點，則 除 υ 外至少還有一個2-鄰點．不妨設(shè) d_G（u₁）=d_G（w₁）=2 ，由引理4知， u₁ 與 不相鄰．由引理7和引理9知， u₂?u₃?w₂?w₃ 均為4-點．下面分兩種情形討論.

情形1） u₁=τν₁ ：

記 為 z 令 G^′=G-z ，則 G^′ 有一個好的染色 φ ，且 |S_φ（w）|=|S_φ（u）|=3 令 由于 d_G^'（u）=3 ，則由引理2中3）知，∣F（uz，u）∣?6. ，又由于 ，因此由引理2中3）知， d_w³?1 ，從而∣F（wz，w）∣?3+1?4 ．因此， α_a，b 存在，將邊 uz 染 a ，邊 wz 染 b ．易驗證 分別與其鄰點互斥.因此該染色是 G 的一個好的染色.

情形2） u₁≠w₁

設(shè) u₁ 除 u 外的另一個鄰點為 u₁^' ， 除 w 外的另一個鄰點為 τυ₁^′ ，由引理 3～ 引理5可知， 均為4-點．令 G^′=G-{v，u₁，w₁} ，則 G^′ 有一個好的染色 φ ，且 |S_φ（u）∣=|S_φ（w）|=2，|S_φ（u₁^′）|= 令 ， ， Λ_c∈C?（F（u₁u，u）? S_φ（u₁^′）∪{a}） ， ， e∈C?（F（uv，u）?S_φ（w）?{a，c，d}）， ．由于 d_G^'（u₁^′）=d_G^'（w₁^′）=3 ，因此由引理2中3）可知，有 ，又由于 d_G^'（u）=d_G^'（w）=2 ，而 d_G^'（u₂）=d_G^'（u₃）= d_G^'（w₂）=d_G^'（w₃）=4 ，因此由引理2中2）可知， d_u²=d_w²=0 ，從而 ∣F（u₁u，u）∣?2 ， 2， ∣F（uv，u）∣?2 ， 故 α，b，c，d，e，f 均存在．將邊 u₁u₁^' 染 Ψ_a ，邊 w₁w₁^′ 染 b ，邊 u₁u 染c ，邊 染 d ，邊 uv 染 e ，邊 wv 染 f .易驗證 u，v，w，u₁，w₁，u₁^′，w₁^′ 與其鄰點均互斥．因此該染色是G 的一個好的染色.

上述兩種情形均可得到 G 的一個好的染色，與 G 是極小反例矛盾．證畢.

2.3 權(quán)轉(zhuǎn)移

為完成定理的證明，在圖 G 上進(jìn)行權(quán)轉(zhuǎn)移分析.

令 |V（G）|=n ．對每個頂點 v∈V（G） ，定義 υ 的初始權(quán)值 ω（υ）=d（υ） ，則初始權(quán)值之和為 ，然后制定權(quán)轉(zhuǎn)移規(guī)則，對權(quán)進(jìn)行重新分配，在該過程中保持權(quán)值的總和不變．設(shè)ω表示調(diào)整后的權(quán)函數(shù)．將證明對任意頂點ε∈V（G）有α≥3， 3，從而推出下列矛盾：

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

1）2-點從相鄰的 4₁- 點得到 1；2）2-點從相鄰的4z-點得到 1；3）3-點從相鄰的4-點得到

權(quán)轉(zhuǎn)移后，每個頂點的終權(quán)如下：若 υ 是2-點，則由引理10知， υ 至少有一個 4₁ -鄰點．根據(jù)權(quán)轉(zhuǎn)移規(guī)則1）和2）， υ 的終權(quán) 若 v 是3-點，則由引理3、引理5和引理6知，的鄰點均為4-點，根據(jù)權(quán)轉(zhuǎn)移規(guī)則3），的終權(quán)ω′≥3+?×3=3gt;3?.

若 υ 是4-點，考慮 v 是 4₁ -點、 4₂- 點及 υ 不含2-鄰點3種情形.

（i）若 υ 是 4₁ -點，則由引理9知， v 的其余3個鄰點均為4-點．根據(jù)權(quán)轉(zhuǎn)移規(guī)則1）， υ 的終權(quán) （ii）若 v 是 4₂- 點，則由引理9知， v 的其余兩個鄰點均為4-點．根據(jù)權(quán)轉(zhuǎn)移規(guī)則2）， υ 的終權(quán) （204（iii）若 υ 不含2-鄰點，則由引理8知， υ 至多含有兩個3-鄰點．根據(jù)權(quán)轉(zhuǎn)移規(guī)則3）， υ 的終權(quán)

因此，任意頂點 Π_v∈V（G） 均有 證畢.

參考文獻(xiàn)

[1]GU J，WANG WF，WANG YQ，et al. Strict Neighbor-Distinguishing Index of Subcubic Graphs [J]. Graphsand Combinatorics，2021，37（1）：355-368.

[2]PRZYBYLO J，KWASNY J. On the Inclusion Chromatic Index of a Graph [J].Journal of Graph Theory， 2021，97（1）：5-20.

[3]ZHANG Z. The Smarandachely Adjacent Vertex Edge Coloring of Graphs [R]. Lanzhou： Lanzhou JiaotongUniversity，2008.

[4]王鴻杰，朱恩強(qiáng)，李敬文．圖的 Smarandachely鄰點邊色數(shù)的界［J]．?dāng)?shù)學(xué)的實踐與認(rèn)識，2017，47（1）：151-155.（WANG H J， ZHU E Q，LI JW. Bounds of Smarandachely Adjacent Vertex Edge Coloring of Graphs [J].JMathematics in Practice and Theory，20l7，47（1）：151-155.）

[5]劉信生，劉旺發(fā)，王志強(qiáng)．圖的 Smarandachely鄰點星邊染色［J]．蘭州大學(xué)學(xué)報（自然科學(xué)版），2012，48（5）：94-97.（LIU X S，LIU W F，WANG Z Q. Smarandachely-Adjacent-Vertex Star Edge Coloring of Graphs [J].Journal of Lanzhou University（Natural Science），20l2，48（5）：94-97.）

[6］劉信生，劉旺發(fā)．圖的 Smarandachely 鄰點無圈邊色數(shù)的一個上界［J]．系統(tǒng)科學(xué)與數(shù)學(xué)，2013，33（5）：550-554.（LIU X S，LIU WF. An Upper Bound on the Smarandachely Adjacent-Vertex Acyclic Edge Coloring ofGraphs[J]. Journal of Systems Science and Mathematical Sciences，2013，33（5）：550-554.）

[7］井普寧，王維凡，王藝橋，等．平面圖的嚴(yán)格鄰點可區(qū)別染色［J]．中國科學(xué)：數(shù)學(xué)，2023，53（3）：523-542.（JING P N，WANG W F，WANG Y Q，et al. Strict Neighbor-Distinguishing Edge Coloring of Planar Graphs[J].Scientia Sinica：Mathematica，2023，53（3）：523-542.）

[8] CHEN L L，LI Y Y. A New Proof for a Result on the Inclusion Chromatic Index of Subcubic Graphs [J].Axioms，2022，11（1）：33-1-33-8.

[9] GU J，WANG Y Q，WANG W F，et al. Strict Neighbor-Distinguishing Index of K₄ -Minor-Free Graphs [J].Discrete Applied Mathematics，2023，329：87-95.

[10]CHEN L L，LI Y Y，ZHOU X Q. The Inclusion-Free Edge-Colorings of （3，Δ） -Bipartite Graphs [J]. DiscreteApplied Mathematics，2022，321：159-164.

[11] 彭燕，談漪，陳莉莉．Halin 圖的無包含邊染色［J]．華僑大學(xué)學(xué)報（自然科學(xué)版），2024，45（6）：812-815.（PENG Y，TAN Y，CHEN L L. Inclusion-Free Edge Colorings of Halin Graph [J]. Journal of HuaqiaoUniversity（Natural Science），2024，45（6）：812-815.）

[12] HUANG N G，CHEN L L. AVD Edge-Colorings of Cubic Halin Graphs [J]. AIMS Mathematics， 2023，8（11） ：27820-27839.

[13] HUANG N G，TAN Y，CHEN L L. On the Inclusion Chromatic Index of a Halin Graph [J]. DiscreteMathematics，2025，348（2）：114266-1-114266-9.

[14] WANG WF，JING P N，GU J，et al.Local Neighbor-Distinguishing Index of Graphs [J]. Bulletin of theMalaysian Mathematical Sciences Society，2023，46（2）：83-1-83-16.

（責(zé)任編輯：趙立芹）