Halin圖的無(wú)包含邊染色

摘要： 探究給定最大度的Halin圖的無(wú)包含邊色數(shù)的上界，通過(guò)分析極小反例圖的結(jié)構(gòu)，在給定部分子圖的染色下，對(duì)剩余圖進(jìn)行特殊染色。結(jié)果表明：最大度為Δ的Halin圖的無(wú)包含邊色數(shù)不超過(guò)Δ+2。

關(guān)鍵詞： Halin圖； 無(wú)包含邊染色； 無(wú)包含邊色數(shù)； 極小反例圖

中圖分類號(hào)： O 157.5文獻(xiàn)標(biāo)志碼： A"" 文章編號(hào)： 1000-5013（2024）06-0812-04

Inclusion-Free Edge Coloring of Halin Graph

PENG Yan， TAN Yi， CHEN Lili

（School of Mathematical Sciences， Huaqiao University， Quanzhou 362021， China）

Abstract： The upper bound of the inclusion-free chromatic index of Halin graph with the given maximum degree is explored. By analyzing the structure of the minimal counterexample graph， the special coloring to the remaining graph is done under the coloring of the given partial subgraphs. The results show that the inclusion-free chromatic index of Halin graph with the maximum degree Δ is" are not more than Δ+2.

Keywords： Halin graph； inclusion-free edge coloring； inclusion-free chromatic index； minimal counterexample graph

1 預(yù)備知識(shí)

設(shè)G是簡(jiǎn)單無(wú)向圖，V（G），E（G），Δ（G）和δ（G）分別表示圖G的頂點(diǎn)集、邊集、最大度和最小度，映射φ：E（G）→C={1，2，3，…，k}為圖G的一個(gè)正常邊染色，即對(duì)任意相鄰邊e1和e2，有φ（e1）≠φ（e2）。對(duì)任意頂點(diǎn)v∈V（G），v關(guān)聯(lián)的邊的顏色集記為Sφ（v），即Sφ（v）={φ（e）邊e與頂點(diǎn)v關(guān)聯(lián)}。

若圖G存在一個(gè)正常的邊染色φ，且滿足對(duì)任意邊uv∈E（G），有Sφ（u）Sφ（v）及Sφ（v）Sφ（u），則稱φ為圖G的無(wú)包含邊染色。使圖G具有無(wú)包含邊染色所需的最小顏色數(shù)稱為圖G的無(wú)包含邊色數(shù)，記為χ′（G）。

無(wú)包含邊染色的概念是由Przybyo等［1］于2020年提出的。 實(shí)際上，Zhang［2］在2008年就提出Smarandachely鄰點(diǎn)邊染色。Gu等［3］將邊染色定義為嚴(yán)格鄰點(diǎn)可區(qū)別邊染色，這類邊染色是對(duì)鄰點(diǎn)可區(qū)別邊染色的推廣。對(duì)于無(wú)孤立邊的圖G，它的鄰點(diǎn)可區(qū)別邊染色是圖G的一個(gè)正常邊染色φ，且滿足對(duì)任意邊uv∈E（G），有Sφ（u）≠Sφ（v）。使圖G具有鄰點(diǎn)可區(qū)別邊染色所需的最小顏色數(shù)稱為圖G的鄰點(diǎn)可區(qū)別邊色數(shù)，記為χ′a（G）。

Zhang［2］確定了路、圈、樹(shù)、完全圖及完全二部圖的鄰點(diǎn)可區(qū)別邊色數(shù)，提出猜想1。

猜想1［2］ "設(shè)G是不為C5的簡(jiǎn)單連通圖，且V（G）≥3，則χ′a（G）≤Δ（G）+2。

定理1［4］ 設(shè)G是沒(méi)有孤立邊的圖，且Δ（G）=3，則χ′a（G）≤5。

Balister等［4］證明對(duì)于最大度為3的圖、所有的二部圖，猜想1是成立的（定理1）。

Hatami［5］使用概率方法證明任意一個(gè)最大度Δ≥1020的圖G，有χ′a（G）≤Δ+300。AKbari等［6］證明任意沒(méi)有孤立邊的圖G，χ′a（G）≤3Δ，Zhang等［7］將這個(gè)上界改進(jìn)到2.5Δ+5。Joret等［8］證明當(dāng)圖G的最大度Δ充分大時(shí)，χ′a（G）≤Δ+19。對(duì)于特殊圖方面，文獻(xiàn)［9-12］得到更多的結(jié)果。

若圖G的最小度δ（G）≥2，則χ′（G）≥χ′a（G），等號(hào)成立當(dāng)且僅當(dāng)G是正則圖。Przybyo等［1］證明若圖G是完全二部圖，那么χ′（G）=1+1δ-1Δ。 對(duì)最大度Δ≥2的完全二部圖K2，Δ，將其中一條邊剖分一次，得到的新圖記為K2，Δ（圖1）。由圖1可知：χ′（K2，Δ）=2Δ+1。

Przybyo等［1］提出一般圖的無(wú)包含邊色數(shù)的猜想，即猜想2。

猜想2［1］ "設(shè)圖G是δ（G）≥2且最大度為Δ的連通圖。 如果G不同構(gòu)于K2，Δ，那么χ′（G）≤1+1δ-1Δ。

Chen等［13］和Gu等［3］分別獨(dú)立地證明了猜想2對(duì)于次立方圖是成立的，Chen等［14］考慮二部圖的無(wú)包含邊染色，得到猜想2對(duì)于（2，Δ）-二部圖是成立的。更多結(jié)果參考文獻(xiàn)［14-16］。

Halin圖是一類平面圖，由樹(shù)T和圈C構(gòu)成，樹(shù)T沒(méi)有2度頂點(diǎn)，C是連接樹(shù)T上所有葉子點(diǎn)構(gòu)成的圈，且圈C是該平面圖外部面的邊界。對(duì)于Halin圖G=T∪C，如果任意的頂點(diǎn)v∈V（G）不是樹(shù)T的葉子點(diǎn)，那么稱頂點(diǎn)v為內(nèi)點(diǎn)，否則，稱頂點(diǎn)v為葉子點(diǎn)。

定理2為Halin圖的無(wú)包含邊染色的結(jié)果。

定理2 設(shè)圖G是最大度為Δ的Halin圖，則χ′（G）≤Δ+2。

由于Δ+2≤Δ+Δδ-1，所以，若定理2成立，則猜想2對(duì)于Halin圖是成立的。

2 定理2的證明

首先，考慮次立方Halin圖。 由Halin圖的定義，次立方Halin圖是3-正則圖。 由于對(duì)任意的正則圖G，有χ′a（G）=χ′（G）。 又由定理1，對(duì)任意無(wú)孤立邊的次立方圖G，有χ′a（G）≤5，從而得到引理1。

引理1 設(shè)圖G=T∪C是次立方Halin圖，則χ′（G）≤5。

對(duì)于次立方Halin圖G，其最大度Δ為3，從而χ′（G）≤5=Δ+2，定理2成立。 因此，始終假設(shè)Halin圖G的最大度Δ至少為4。

引理2 對(duì)任意的k≥4，設(shè)Halin圖G=T∪C的最大度為k，且只含一個(gè)內(nèi)點(diǎn)，則χ′（G）≤k+2。

證明：假設(shè)頂點(diǎn)v是Halin圖G的唯一內(nèi)點(diǎn)，v1，v2，…，vk是v的所有鄰點(diǎn)，不失一般性，設(shè)圈C=v1v2…vk。對(duì)i=1，2，…，k，令φ（vvi）=i。 如果k是偶數(shù)，則當(dāng)i=1，3，…，k-1時(shí)，令φ（vivi+1）=k+1，當(dāng)i=2，4，…，k-2時(shí)，令φ（vivi+1）=k+2，最后，令φ（vkv1）=k+2；如果k是奇數(shù)，則當(dāng)i=1，3，…，k-2時(shí)，令φ（vivi+1）=k+1，當(dāng)i=2，4，…，k-1時(shí)，令φ（vivi+1）=k+2，最后，令φ（vkv1）=2。 易驗(yàn)證，φ是圖G的一個(gè)無(wú)包含邊染色，因此χ′（G）≤k+2。

均假設(shè)圖G至少含有2個(gè)內(nèi)點(diǎn)，有引理3。

引理3 設(shè)Halin圖G=T∪C至少含2個(gè)內(nèi)點(diǎn)，則G中存在一個(gè)內(nèi)點(diǎn)w，w只有一個(gè)鄰點(diǎn)是內(nèi)點(diǎn)，其余鄰點(diǎn)都是樹(shù)T的葉子點(diǎn)。

證明：假設(shè)G中不存在這樣的內(nèi)點(diǎn)，即任意內(nèi)點(diǎn)的鄰點(diǎn)中至少有2個(gè)是內(nèi)點(diǎn)。 設(shè)G的所有內(nèi)點(diǎn)導(dǎo)出的子圖為T′，由假設(shè)可得δ（T′）≥2，因此T′不是樹(shù)。 但是，T′是T的子圖，即T′是樹(shù)，矛盾。 因此，假設(shè)不成立。 引理3得證。

稱滿足引理3的內(nèi)點(diǎn)w為完美點(diǎn)。

引理4 設(shè)Halin圖G=T∪C至少含2個(gè)內(nèi)點(diǎn)，且最大度Δ≥4，則χ′（G）≤Δ+2。

證明：假設(shè)G=T∪C是滿足引理?xiàng)l件的極小反例。設(shè)w是圖G的一個(gè)完美點(diǎn)，u是w的鄰點(diǎn)中的唯一內(nèi)點(diǎn)，v1，v2，…，vk是w在圈C上的鄰點(diǎn)，對(duì)i=1，…，k-1，vivi+1∈E（G）。 設(shè)v1在圈上的另一個(gè)鄰點(diǎn)為x，vk在圈上的另一個(gè)鄰點(diǎn)為y。 記x的鄰點(diǎn)為v1，x1，x2；y的鄰點(diǎn)為vk，y1，y2。 不失一般性，假設(shè)x2，y2在圈C上。完美點(diǎn)w及鄰點(diǎn)，如圖2所示。假設(shè)F={1，2，…，Δ+2}為含有Δ+2種顏色的色集。

情形1 當(dāng)d（w）=3時(shí)，令G′=G-{v1，v2}+{xw，yw}，顯然，G′仍是Halin圖且V（G′）lt;V（G）。由G的極小性，有χ′（G′）≤Δ（G′）+2≤Δ+2。 設(shè)φ′是定義在色集F上的G′的一個(gè)無(wú)包含邊染色，不失一般性，假設(shè)φ′（xw）=a， φ′（yw）=b， φ′（wu）=c。

首先，對(duì)任意的邊e∈E（G）∩E（G′），令φ（e）=φ′（e）。 對(duì)于邊xv1，yv2，令φ（xv1）=a， φ（yv2）=b。 因?yàn)镾φ′（w）Sφ′（u），所以{a，b}中至少存在一個(gè)顏色不在Sφ′（u）中，不妨設(shè)aSφ′（u）。 將邊wv2染顏色a，從而aSφ（u）但a∈Sφ（w）。又因?yàn)閐（w）≤d（u），所以Sφ（u）Sφ（w）且Sφ（w）Sφ（u）。

其次，因?yàn)棣ぁ?，所以Δ+2≥6，從而F＼{a，b，c，φ（xx1），φ（xx2）}≥1。 因此，可以在F＼{a，b，c，φ（xx1），φ（xx2）}中選取一個(gè)顏色d，將邊wv1染顏色d。 因?yàn)閐Sφ（x），但d∈Sφ（v1），所以Sφ（v1）Sφ（x）且Sφ（x）Sφ（v1）。

最后，如果aSφ（y），則可以在F＼{a，b，c，d}中選一個(gè)顏色d1對(duì)邊v1v2進(jìn)行染色。 若a∈Sφ（y）， 不妨設(shè)φ（yy1）=a， 則可以在F＼{a，b，c，d，φ（yy2）}選一個(gè)顏色d′1對(duì)邊v1v2進(jìn)行染色。

易驗(yàn)證，該染色φ是G的一個(gè)無(wú)包含邊染色，且使用顏色總數(shù)為Δ+2，因此χ′（G）≤Δ+2，與假設(shè)矛盾。

情形2 當(dāng)d（w）≥4時(shí)，令G′=G-{v1，v2，…，vk}+{xw，yw}，顯然，G′仍是Halin圖且V（G′）lt;V（G）。由G的極小性，可得χ′（G′）≤Δ（G′）+2≤Δ+2。設(shè)φ′是定義在色集F上的G′的一個(gè)無(wú)包含邊染色，不失一般性，假設(shè)φ′（xw）=a，φ′（yw）=b，φ′（wu）=c。

首先，對(duì)任意的邊e∈E（G）∩E（G′），令φ（e）=φ′（e）。 對(duì)于邊xv1，wvk，yvk，wv1，令φ（xv1）=φ（wvk）=a，φ（yvk）=φ（wv1）=b。 因?yàn)镾φ′（w）Sφ′（u），所以{a，b}中至少存在一個(gè)顏色不在Sφ′（u）中，不妨設(shè)aSφ′（u）。 同理，因?yàn)镾φ′（u）Sφ′（w），所以Sφ′（u）中至少存在一個(gè)顏色不在{a，b，c}中，記這些顏色中的一個(gè)為γ。 由于{wv2，…，wvk-1}=k-2，且d（w）=k+1≤Δ，因此k-2≤Δ-1-2=Δ-3。 又因?yàn)镕＼{a，b，c，γ}≥Δ+2-4=Δ-2，所以可以用F＼{a，b，c，γ}中的不同顏色分別對(duì)邊wv2，…，wvk-1進(jìn)行染色。 不失一般性，對(duì)i=2，3，…，k-1，令φ（wvi）=di。 在當(dāng)前染色下，Sφ（u）Sφ（w）且Sφ（w）Sφ（u）。

其次，假設(shè)φ（xx1）=c1，φ（xx2）=c2，φ（yy1）=c3，φ（yy2）=c4。 易知，F(xiàn)＼Sφ（w）≥2，不妨假設(shè){α，β}∈F＼Sφ（w）。

如果{c1，c2}={α，β}，則Sφ（x）={a，α，β}。 由于b∈Sφ（w），因此b{α，β}，從而可以使用{α，β}中的任意一個(gè)顏色給邊v1v2染色，使得Sφ（x）Sφ（v1）且Sφ（v1）Sφ（x）。 如果{c1，c2}≠{α，β}，不失一般性，不妨設(shè)α{c1，c2}，那么可以使用α給邊v1v2染色，使得Sφ（x）Sφ（v1）且Sφ（v1）Sφ（x）。 同理，可以使用{α，β}中至少一個(gè)顏色給邊vk-1vk染色，使得Sφ（y）Sφ（vk）且Sφ（vk）Sφ（y）。

如果α，β均可以給邊v1v2染色，使得Sφ（x）Sφ（v1）且Sφ（v1）Sφ（x），則先給邊vk-1vk染色，然后交替使用α，β依次對(duì)邊vk-2vk-1，vk-3vk-2，…，v1v2進(jìn)行染色，使其滿足φ（vk-2vk-1）≠φ（vk-1vk）。 如果α，β中只有一個(gè)顏色可以給邊v1v2染色，使得Sφ（x）Sφ（v1）且Sφ（v1）Sφ（x），則{α，β}∩{c1，c2}=1。 不失一般性，假設(shè)α=c1，則β≠c2。如果b≠c2，則α，β均可以給邊v1v2染色，與假設(shè)矛盾，故b=c2。交換wv1和wv2的顏色，即φ（wv1）=d2，φ（wv1）=b。 交換后，α，β均可以給邊v1v2染色。 因此，先給邊vk-1vk染色，然后交替使用α，β依次對(duì)邊 vk-2vk-1，vk-3vk-2，…，v1v2進(jìn)行染色，使其滿足φ（vk-2vk-1）≠φ（vk-1vk）。

綜上，構(gòu)造圖G的一個(gè)邊染色φ，得到Sφ（u）Sφ（w）且Sφ（w）Sφ（u），Sφ（x）Sφ（v1）且Sφ（v1）Sφ（x）及Sφ（y）Sφ（vk）且Sφ（vk）Sφ（y）。 因?yàn)閎≠d2，a≠dk-1，di≠di+1，i=2，3，…，k-2，所以對(duì)i=1，2，…，k-1，有Sφ（vi）Sφ（vi+1）且Sφ（vi+1）Sφ（vi）。最后，由于α，β至少有一個(gè)屬于Sφ（vi），而α，β均不屬于且Sφ（w），因此對(duì)i=1，2，…，k，有Sφ（vi）Sφ（w）且Sφ（w）Sφ（vi）。 因此，φ是G的一個(gè)無(wú)包含邊染色，且使用顏色總數(shù)為Δ+2，即χ′（G）≤Δ+2，與假設(shè)矛盾。引理4得證。

綜合引理1、引理2和引理4，定理2得證。

3 結(jié)束語(yǔ)

通過(guò)研究極小反例Halin圖G的子圖的染色結(jié)構(gòu)，得到圖G的Δ+2種顏色的無(wú)包含邊染色，與G是極小反例矛盾，從而證明G的無(wú)包含邊色數(shù)不超過(guò)Δ+2。

參考文獻(xiàn)：

［1］ PRZYBYLO J，KWASNY J.On the inclusion chromatic index of a graph［J］.Journal of Graph Theory，2021，97（1）：5-20.DOI：10.1002/jgt.22636.

［2］ ZHANG Zhongfu.The Smarandachely adjacent vertex edge coloring of graphs［R］.Lanzhou：Lanzhou Jiaotong University，2008：1-13.

［3］ GU Jing，WANG Weifan，WANG Yiqiao，et al.Strict neighbor-distinguishing index of subcubic graphs［J］.Graphs and Combinatorics，2021，37：355-368.DOI：10.1007/s00373-020-02246-w.

［4］ BALISTER P N，GYORI E，LEHEL J，et al.Adjacent vertex distinguishing edge-colorings［J］.SIAM Journal on Discrete Mathematics，2007，21（1）：237-250.DOI：10.1137/S0895480102414107.

［5］ HATAMI H.Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number［J］.Journal of Combinatorial Theory Series B，2005，95：246-256.DOI：10.1016/j.jctb.2005.04.002.

［6］ AKBARI S，BIDKHORI H，NOSTRATI N.R-strong edge colorings of graphs［J］.Discrete Mathematics，2006，306：3005-3010.DOI：10.1016/j.disc.2004.12.027.

［7］ ZHANG Lianzhu，WANG Weifan，LIH Kowei.An improved upper bound on the adjacent vertex distinguishing chromatic index of a graph［J］.Discrete Applied Mathematics，2014，162：348-354.DOI：10.1016/j.dam.2013.08.038.

［8］ JORET G，LOCHET W.Progress on the adjacent vertex distinguishing edge coloring conjecture［J］.SIAM Journal on Discrete Mathematics，2020，34（4）：2221-2238.DOI：10.1137/18M1200427.

［9］ BU Yuehua，LIH KW，WANG Weifan.Adjacent vertex-distinguishing edge-colorings of planar graphs withgirth at least six［J］.Discussiones Mathematicae Graph Theory，2011，31（3）：429-439.DOI：10.7151/dmgt.1556.

［10］ YAN Chengchao，HUANG Danjun，CHEN Dong，et al.Adjacent vertex distinguishing edge colorings of planar graphs with girth at least five［J］.Journal of Combinatorial Optimization，2014，28（4）：893-909.DOI：10.1007/s10878-012-9569-5.

［11］ WANG Weifan，WANG Yiqiao.Adjacent vertex-distinguishing edge coloring of K4-minor-free graphs［J］.Applied Mathematics Letters，2011，24（12）：2034-2037.DOI：10.1016/j.aml.2011.05.038.

［12］ WANG Yi，CHENG Jian，LUO Rong，et al.Adjacent vertex-distinguishing edge coloring of 2-degenerate graphs［J］.Journal of Combinatorial Optimization，2016，31：874-880.DOI 10.1007/s10878-014-9796-z.

［13］ CHEN Lili，LI Yanyi.A new proof for a result on the inclusion chromatic index of subcubic graphs［J］.Axioms，2022，11：33.DOI：10.3390/axioms11010033.

［14］ CHEN Lili，LI Yanyi，ZHOU Xiangqian.The inclusion-free edge-colorings of （3，Δ）-bipartite graphs［J］.Discrete Applied Mathematics，2022，321：159-164.DOI：10.1016/j.dam.2022.06.039.

［15］ GU Jing，WANG Yiqiao，WANG Weifan，et al.Strict neighbor-distinguishing index of K4-minor-free graphs［J］.Discrete Applied Mathematics，2023，329：87-95.DOI：10.1016/j.dam.2023.01.017.

［16］ JING Puning，WANG Weifan，WANG Yiqiao，et al.Strict neighbor-distinguishing edge coloring of planar graphs［J］.Scientia Sinica Mathematica，2023，53（3）：523-542.DOI：10.1360/SSM-2021-0178.

（責(zé)任編輯： "陳志賢" 英文審校： 黃心中）

通信作者： 陳莉莉（1986-），女，副教授，博士，主要從事圖染色的研究。E-mail：lily60612@126.com。

基金項(xiàng)目： 中央高?；究蒲袠I(yè)務(wù)經(jīng)費(fèi)專項(xiàng)資金資助項(xiàng)目（ZQN-903）https：//hdxb.hqu.edu.cn/