一類圖的列表強(qiáng)邊染色

黃會(huì)蕓

（南京化工職業(yè)技術(shù)學(xué)院，江蘇南京 210048）

一類圖的列表強(qiáng)邊染色

黃會(huì)蕓

（南京化工職業(yè)技術(shù)學(xué)院，江蘇南京 210048）

給出了列表強(qiáng)邊染色的定義，證明了若G為d（x）＋d（y）≤5，則強(qiáng)邊選擇數(shù)Sχ′l（G）≤6.

染色；強(qiáng)邊染色；強(qiáng)邊色數(shù)；列表強(qiáng)邊染色；強(qiáng)邊選擇數(shù)

1 基本概念和主要結(jié)論

僅考慮有限、無(wú)向、無(wú)環(huán)但可以有平行邊的圖.用G（V，E）來(lái)表示圖，其中V表示圖G的頂點(diǎn)集，E表示圖G的邊集.圖G的一個(gè)k－邊正常染色是指一個(gè)映射φ：E（G）→｛1，2，…，k｝，若對(duì)任何2個(gè)相鄰的邊e和e′，均有φ（e）＝φ（e′），簡(jiǎn)稱為圖G的一個(gè)k－邊染色或稱該圖是k－邊可染的，最小的整數(shù)k稱為G的邊色數(shù)，記為χ′（G）.

圖G的k－強(qiáng)邊染色是正常k－邊染色，使得沒有相鄰于具有相同顏色的2條邊.若圖G存在k－強(qiáng)邊染色，則稱圖G是k－強(qiáng)邊可染的.圖G的強(qiáng)邊色數(shù)是使得G是k－強(qiáng)邊可染的最小的整數(shù)k，記為sχ′（G）.圖G的部分強(qiáng)邊著色是指一個(gè)滿足上述條件的著色，除了G的某些邊未被著色.

文獻(xiàn)［1］中提出一個(gè)公開問(wèn)題：如果G是二部圖，圖中的任意一條邊xy∈E（G），那么d（x）＋d（y）≤5.文獻(xiàn)［2］中證明若d（x）＋d（y）≤5，則sχ′（G）≤6.

給G的每條邊e分配一個(gè)顏色列表L（e），稱G是L－強(qiáng)邊染色的是指對(duì)每條邊e，都可從其對(duì)應(yīng)列表中L（e）找到一種染色f（e）∈L（e），使得f是G的一個(gè)強(qiáng)邊染色.如果每條邊列表長(zhǎng)度都相同，此時(shí)強(qiáng)邊著色數(shù)（或強(qiáng)邊選擇數(shù)）定義為滿足下面條件的最小的正整數(shù)k，使對(duì)G的任一邊e，只要當(dāng)｜L（e）｜≥k時(shí)，G都是L強(qiáng)邊可染的.設(shè)L為G的任意一個(gè)邊列表分配，G的部分L－強(qiáng)邊染色是部分強(qiáng)邊染色f使得對(duì)于任意e∈E?E（G），有f（e）∈L（e）.

圖1 H0

文獻(xiàn)［3］中得到如下結(jié)論：當(dāng)Δ（G）≤3且δ（G）≤2，則）≤10；若G為3正則圖，當(dāng)g（G）＝3時(shí)≤10；若G為3正則圖，當(dāng)g（G）≥4時(shí)

筆者將證明：除了圖H0的列表強(qiáng)邊色數(shù)等于7以外，當(dāng)圖的最大邊度數(shù)小于等于5時(shí)，列表強(qiáng)邊色數(shù)小于等于6.其中H0的構(gòu)造如下：給定一個(gè)5圈，再增加1個(gè)頂點(diǎn)，將這個(gè)頂點(diǎn)與5圈的2個(gè)不相鄰的頂點(diǎn)相連.可以看出H0有7條邊，任意2條邊之間的距離不超過(guò)2（如圖1所示），從而有＝7.即證明：

定理1 給定圖G，G不同構(gòu)于H0，若對(duì)圖G的任一條邊x y，滿足d（x）＋d（y）≤5，則當(dāng)二度點(diǎn)相鄰時(shí)，有≤6；當(dāng)二度點(diǎn)不相鄰時(shí)，有≤7.

2 對(duì)圖的邊進(jìn)行排序

文獻(xiàn)［4］利用貪心算法構(gòu)造3正則圖的一個(gè)部分強(qiáng)邊著色并介紹了圖的邊排序的方法.筆者也將借用這種方法，給圖進(jìn)行邊排序后，再利用貪心算法得到一個(gè)部分強(qiáng)邊著色.

S是V（G）的頂點(diǎn)子集，頂點(diǎn)v∈V（G），dS（v）表示v到S的距離，定義為是V（G）的頂點(diǎn)子集，I表示從V（G）中的一個(gè)點(diǎn)到的S最大距離.設(shè)Di＝｛v∈V（G）｜d（v，S）＝i｝（i＝0，1，…，I）.定義一個(gè)從E（G）到［0，I］的映射dS如下：對(duì)任意一條邊e∈E（G），dS（e）＝min｛i｜e∩Di≠?，0≤i≤I｝.S是V（G）的頂點(diǎn)子集，R＝（ek1，ek2，…，ekm）是圖G的一個(gè)邊序列.對(duì)任意2正整數(shù)i，j∈［1，m］，如果ki≤kj意味著dS（eki）≥dS（ekj），就稱圖G的邊序列R關(guān)于映射dS是可比較的.

設(shè)E（G）中的任一條邊e，E（G）的強(qiáng)領(lǐng)域N（e）是E（G）中與e的距離小于等于2的邊集合.令f為圖G的部分L－強(qiáng)邊著色，對(duì)于未染色邊e，E（G）為部分強(qiáng)邊染色邊集.使用F（e）表示的禁用顏色集合，F(xiàn)（e）＝｛f（e′）｜1≤dG（e，e′）≤2，e′∈E′｝.

Hall定理 設(shè)A1，A2，…，Am是集合S的m個(gè)子集，子集族A＝｛A1，A2，…，Am｝的一個(gè)相異代表系SDR是指S的一個(gè)子集合｛a1，a2，…，am｝滿足：（?。゛i∈Ai，i∈｛1，…，m｝；（ⅱ）對(duì)于任意i≠j，有ai≠aj.子集族A存在SDR當(dāng)且僅當(dāng)對(duì)于任意子集J?｛1，…，m｝有｜∪i∈jAi｜≥｜J｜.

引理1 設(shè)G是一個(gè)連通圖，當(dāng)圖的最大邊度數(shù)小于等于5，L為G的任意一個(gè)邊列表分配，設(shè)對(duì)任意一條邊e，｜L（e）｜＝6，S是V（G）的任意頂點(diǎn)子集，R是圖G的關(guān)于映射dS的可比較的邊序列，除了滿足dS（e）＝0的邊外，利用貪心算法對(duì)邊序列R進(jìn)行著色，即可產(chǎn)生圖G的一個(gè)部分強(qiáng)邊著色.

證明 如果e是滿足dS（e）≥0的一條邊，那么一定存在另一條邊e′，e和e′有一公共的端點(diǎn)，并且dS（e′）≤dS（e）.設(shè)x是e和e′的公共端點(diǎn)，y是e′的另一端點(diǎn)，當(dāng)利用貪心算法對(duì)e邊著色時(shí)，與y關(guān)聯(lián)的邊還沒著色.設(shè)L為G的任意邊列表分配，定義e的禁用顏色集合F（e）.從圖的結(jié)構(gòu)可知｜F（e）｜≤5，即從｜L（e）｜＝6的列表中總可以挑出1種顏色給邊e，使邊e進(jìn)行正常的L－強(qiáng)邊著色.

3 d（x）＋d（y）≤5圖的強(qiáng)邊選擇數(shù)

3.1 樹的列表強(qiáng)邊染色

定理2 若G是樹，則sχ′l（T）＝sχ′（T）＝σ（G

證明 設(shè)A為G中度為1的頂點(diǎn)的集合，設(shè)uv為V（G）－A所展開的樹圖的一條邊，令u在T的度為1，任取ω∈A，使uw∈E（G）.設(shè)L為G的任意一個(gè)邊列表分配，使得對(duì)任意e∈E（G），有｜L（e）｜＝σ（G）.假設(shè)對(duì)樹G－ω命題成立，即對(duì)G－ω每條邊均能從長(zhǎng)度為σ（G－ω）的列表中選取1種顏色來(lái)上色.對(duì)于未著色的邊uw∈E（G）有最多dG－w（u）＋dG－w（v）＜dG（u）＋dG（v）－1＜σ（G）種禁用色，所以對(duì)于uω從它的長(zhǎng)度為σ（G）的列表中存在至少1種未用的顏色分配給uω.

3.2 圈的列表強(qiáng)邊染色

定理3 設(shè)Cn是長(zhǎng)度為n的圈，則

證明 L為G的任意一個(gè)邊列表分配，f為G的L－強(qiáng)邊染色.對(duì)于任意未染色邊e都定義一個(gè)可利用顏色列表L′（e）＝L（e）＼F（e），使得G中任意邊e，均有｜L（e）｜＝3.

設(shè)圖G的6圈為C＝v1v2v3v4v5v6，令e1＝v1v2，e2＝v2v3，e3＝v3v4，e4＝v4v5，e5＝v5v6，e6＝v6v1.

情形1 若L（e1）∩L（e4）＝?且L（e2）∩L（e5）＝?且L（e3）∩L（e6）＝?.令子集族e(cuò)＝｛e1e2e3e4e5e6｝，對(duì)任意子集J?｛1，2，3，4，5，6｝，都有｜UL′（ei）｜≥｜J｜，故子集族e(cuò)存在SDR，即G是L－強(qiáng)邊可染的.

情形2 若L（e1）∩L（e4）≠?或L（e2）∩L（e5）≠?或L（e3）∩L（e6）≠?.設(shè)f為G的L－強(qiáng)邊染色.不妨令f（e1）＝f（e4）＝a∈L（e1）∩L（e4）.給e2，e3，e5的顏色分別為b，c，d.對(duì)e6而言，若L（e6）≠｛a，b，d｝，則命題成立.若L（e6）＝｛a，b，d｝，考慮e5，若L（e5）≠｛a，c，d｝則將e5換色，命題成立.假設(shè)L（e5）＝｛a，c，d｝，再考慮e3，若L（e3）≠｛a，b，c｝則將e3換色，命題成立.若L（e3）＝｛a，b，c｝，有f（e3）＝f（e6）＝b，f（e1）＝f（e4）＝a，則e2，e5可正常染色，命題成立.

定理4 設(shè)Cn是長(zhǎng)度為n的圈，則

由定理3得Sχ′l（C6）＝3.下證當(dāng)n≥6且n≠3k時(shí)

設(shè)圈Cn＝v1v2v3v4v5v6…vn，ei＝vivi＋1，i＝1，…，n－i，en＝vnv1.設(shè)L為G的任意一個(gè)邊列表分配.f為G的L－強(qiáng)邊染色.對(duì)于任意未染色邊e都定義一個(gè)可利用顏色列表L′（e）＝L（e）＼F（e）.

情形1 L（e1）∩L（e4）≠?.不妨令f（e1）＝f（e4）＝a∈L（e1）∩L（e4）.從e2開始一直到en依次著色，可以看出｜L′（e2）｜≥3，｜L′（e3）｜≥2，｜L′（e5）｜≥2，｜L′（e6）｜≥2，…，｜L′（en－1）｜≥2，｜L′（en）｜≥1，即｜L（e）｜＝4，可以得到L－強(qiáng)邊染色.

情形2 L（e1）∩L（e4）＝?，先對(duì)e5從開始一直到en依次著色，｜L（e）｜＝4，可以得到L－強(qiáng)邊染色.對(duì)于邊e1e2e3e4，｜L′（e1）｜≥2，｜L′（e2）｜≥3，｜L′（e3）｜≥3，｜L′（e4）｜≥2，由L（e1）∩L（e4）＝?，則｜L′（e1）∪L′（e4）｜≥4，對(duì)于任意子集J?｛1，2，3，4｝都有｜∪L′（ei）｜≥｜J｜（i＝1，2，3，4），故L′存在SDR，根據(jù)Hall定理用｜L（e）｜＝4，就可以得到L－強(qiáng)邊染色.

假設(shè)G是連通圖，若Δ（G）＝4，則G同構(gòu)于k1，4，顯然）＝4；若Δ（G）＝1，則.下面分別證明Δ（G）＝2，Δ（G）＝3的情形，定理1的證明由下面一系列的定理組成.

3.3 Δ（G）＝2的圖的列表強(qiáng)邊染色

定理5 設(shè)Pn是n個(gè)頂點(diǎn)的路，則

3.4 Δ（G）＝3的圖的列表強(qiáng)邊染色

證明 設(shè)v0是度為1的頂點(diǎn)，e0是和v0關(guān)聯(lián)的邊.由圖G的結(jié)構(gòu)可知，令S＝｛v0｝，由引理1，除e0外所有邊是L－強(qiáng)邊可染的.由于｜N（e0）｜≤4，因此邊e0也可正常著色.從而，≤5≤6，即命題成立.

下面假定圖G沒有度為1的頂點(diǎn).

定理7 如果圖g（G）＝2或3，那么Sχ′l（G）≤6.

證明 設(shè)S是由圖G中最小圈的頂點(diǎn)組成的集合.首先利用貪心算法對(duì)G中所有滿足dS（e）≥0的邊進(jìn)行著色.當(dāng)g（G）＝2時(shí)，｜L′（e0）｜≥3，｜L′（e1）｜≥5，｜L′（e2）｜≥5，對(duì)于任意子集J?｛0，1，2｝都有｜UL′（ei）｜≥｜J｜（i＝0，1，2），故L′存在SDR，根據(jù)Hall定理用｜L（e）｜＝6就可以得到L－強(qiáng)邊染色.同理，當(dāng)g（G）＝3時(shí)，｜L′（e0）｜≥3，｜L′（e1）｜≥5，｜L′（e2）｜≥6，｜L′（e3）｜≥5，故L′存在SDR，根據(jù)Hall定理，Sχ′l（G）≤6，即命題成立.

定理8 如果圖g（G）＝4，那么Sχ′l（G）≤6.

證明 設(shè)L是圖G的任意一個(gè)邊列表分配，使得對(duì)任意e∈E（G），有｜L（e）｜＝6.設(shè)?為G的部分L－強(qiáng)邊染色，對(duì)于任意未染色邊e都定義一個(gè)可利用顏色列表L′（e）＝L（e）＼F（e）.當(dāng)｜E（G）≤6｜時(shí)，顯然命題成立.假設(shè)｜E（G）｜＞6，設(shè)圖G的4－圈為C＝v1v2v3v4，并設(shè)S＝V（C）.如果在C中至多有1個(gè)3度點(diǎn)，首先利用貪心算法對(duì)G中所有滿足dS（e）≥0的邊進(jìn)行著色，那么｜L′（e0）｜≥3，｜L′（e1）｜≥5，｜L′（e2）｜≥6，｜L′（e3）｜≥6，｜L′（e4）｜≥5，故L′存在SDR，根據(jù)Hall定理用｜L（e）｜＝6，就可以得到L－強(qiáng)邊染色.

下面考慮C中恰好有2個(gè)不相鄰的3度點(diǎn)的情形.

不妨設(shè)d（v1）＝d（v3）＝3，設(shè)與v1和v3相鄰的點(diǎn)分別為u1和u3，令e1＝v1v2，e2＝v2v3，e3＝v3v4，e4＝v4v1，f1＝v1u1，f3＝v3u3.如果u1＝u3，那么G與K2，3同構(gòu)，顯然Sχ′l（K2，3）≤6.假設(shè)u1≠u3，如果u1u3∈E（G），那么G與H0同構(gòu).因此，假設(shè)u1u3?E（G），設(shè)u1的另一鄰點(diǎn)是ω1，u3的另一鄰點(diǎn)是ω3.首先利用貪心算法對(duì)G中所有滿足dS（e）≥0的邊進(jìn)行著色.下面將?擴(kuò)展成整個(gè)圖的L－強(qiáng)邊著色.

情形1 若L′（f1）∩L′（f3）≠?，則可令?（f1）＝?（f3）∈L′（f1）∩L′（f3），此時(shí)可看出，｜L′（ei）｜≥4（i＝1，2，3，4），所以可以從L′（ei）中挑出1種顏色給每條邊著色，從而得到圖G的｜L（e）｜＝6的L－強(qiáng)邊著色.

情形2 若L′（f1）∩L′（f3）＝?，對(duì)于任意子集J?｛i，j｝（i＝1，2，3；j＝1，3）都有｜∪L′（ei）∪L′（fj）｜≥｜J｜，則L′＝｛L′（e）｜e為未染色邊｝存在SDR，那么?擴(kuò)展到G.

證明 設(shè)C＝v1v2v3v4v5v1是圖G的一個(gè)5－圈，并設(shè)S＝v（C）.設(shè)?為G的部分L－強(qiáng)邊染色，下面將?擴(kuò)展到G.對(duì)于任意未染色邊e都定義一個(gè)可利用顏色列表L′（e）.如果在C中至多有1個(gè)3度點(diǎn)，首先利用貪心算法對(duì)G中所有滿足dS（e）≥0的邊進(jìn)行著色，那么｜L′（e0）｜≥3，｜L′（e1）｜≥6，｜L′（e2）｜≥5，｜L′（e3）｜≥5，｜L′（e4）｜≥6，｜L′（e5）｜≥6，對(duì)于任意子集J?｛0，1，2，3，4，5｝都有｜∪L′（ei）｜≥｜J｜（i＝0，1，2，3，4，5），故L′存在SDR，根據(jù)Hall定理用｜L（e）｜＝6，就可以得到L－強(qiáng)邊染色.

下面考慮C中恰好有2個(gè)不相鄰的3度點(diǎn)的情形.

圖2 圖G圍長(zhǎng)為5

不妨設(shè)d（v1）＝d（v3）＝3，設(shè)與v1和v3相鄰的點(diǎn)分別為u1和u3，令e1＝v1v2，e2＝v2v3，e3＝v3v4，e4＝v4v5，e5＝v5v1，f1＝v1u1，f3＝v3u3，由于G沒有4－圈，因此必有u1≠u3.如果u1u3∈E（G），如圖2所示，先用｜L（e）｜＝6對(duì)e1e2e3e4e5進(jìn)行L－強(qiáng)邊著色.對(duì)于剩下3條邊f(xié)1，f3，t1，｜L′（f1）｜≥2，｜L′（f2）｜≥2，｜L′（t1）｜≥2.又因?yàn)镕（f3）＝｛e1e2e3e4｝，F(xiàn)（f1）＝｛e1e2e4e5｝，F(xiàn)（t1）＝｛e1e2e3e5｝，｜∪L′（f1）∪L′（f2）∪L′（t1）｜≥3，所以L′存在SDR，根據(jù)Hall定理用｜L（e）｜＝6，就可以得到L－強(qiáng)邊染色.現(xiàn)在考慮u1u3?E（G），設(shè)u1的另一鄰點(diǎn)是ω1，u3的另一鄰點(diǎn)是ω3.t1＝u1ω1，t3＝u3ω3，首先利用貪心算法對(duì)G中所有滿足dS（e）≥0的邊進(jìn)行著色.若L′（f1）∩L′（f3）≠?，則可令?（f1）＝?（f3）∈L′（f1）∩L′（f3），此時(shí)可看出｜L′（ei）｜≥4（i＝1，2，3，5），｜L′（e4）｜≥5，這樣可以按照邊的次序e3e2e1e5e4，從每條邊ei的L′（ei）中選取1種顏色給這5條邊著色，從而將?擴(kuò)充成整個(gè)圖G的L－強(qiáng)邊著色.若L′（f1）∩L′（f3）＝?，則對(duì)于未著色的7條邊，｜L′（e4）｜＝6（i＝1，2，3，5），｜L′（ei）｜≥5（i＝1，2，3，5），｜L′（fi）｜≥3（i＝1，3）.（），｛，｝（，，，，；，），

情形1∪L′f3｜＝7對(duì)于任意子集J?i j i＝1 2 3 4 5 j＝1 3都有｜∪L′（ei）∪L′（fj）｜≥｜J｜，則L′＝｛L′（e）｜e為未染色邊｝存在SDR，那么?擴(kuò)展到G.

定理10 如果圖g（G）＝6，那么Sχ′l（G）≤6.

證明 設(shè)C＝v1v2v3v4v5v6v1是圖G的一個(gè)6－圈，并設(shè)S＝v（C）.首先利用貪心算法對(duì)G中所有滿足dS（e）≥0的邊進(jìn)行著色.設(shè)?為G的部分L－強(qiáng)邊染色，那么｜L′（ei）｜≥3（i＝1，2，3，4，5，6）.根據(jù)定理3知可以將?擴(kuò)展到G.

定理11 如果G有2個(gè)相鄰的度為2的點(diǎn)，且g（G）≥7，那么Sχ′l（G）≤6.

圖3 圖G圍長(zhǎng)至少為7

證明 由定理7，8，9，10，可假設(shè)G的圍長(zhǎng)至少是7.設(shè)v1，v2是2個(gè)相鄰的度為2的點(diǎn)，如圖3所示.設(shè)與v1，v2相鄰的點(diǎn)分別為u1，u2，設(shè)e1＝v1v2，f1＝v1u1，f2＝v2u2，設(shè)N（u1）＝｛v1w1w2｝，N（u2）＝｛v2w3w4｝.由于G中沒有圈長(zhǎng)小于6的圈，也沒有度為1的點(diǎn)，因此w1w2w3w4是度為2的4個(gè)不同點(diǎn)，g1＝u1w1，g2＝u2w2，g3＝u2w3，g4＝u2w4.設(shè)L為G的任意一個(gè)邊列表分配，對(duì)于任意未染色的邊e定義一個(gè)可利用顏色列表L′（e），?為G的部分L－強(qiáng)邊染色，令S＝｛v1，v2，u1，u2｝.利用貪心算法對(duì)滿足dS（e）≥0的邊進(jìn)行部分L－強(qiáng)邊染色，此時(shí)｜L′（e1）｜≥6，｜L′（fi）｜≥4，｜L′（gi）｜≥2.，｛，，｝（；，；，，，）（）

情形1 ≥7對(duì)于任意子集J?i j k i＝1 j＝1 2 k＝1 2 3 4都有｜∪L′ei∪L′（fj）∪L′（gk）｜≥｜J｜，則L′＝｛L′（e）｜e為未染色邊｝存在SDR，那么?擴(kuò)展到G.

圖4 圖G的圍長(zhǎng)至少為8

證明 假定G是連通圖并且沒有1度點(diǎn).設(shè)v0是度為2的點(diǎn)且N（v0）＝｛u1u2｝，如圖4所示.設(shè)L為G的任意一個(gè)邊列表分配，對(duì)于任意未染色的邊e定義一個(gè)可利用顏色列表L′（e）.設(shè)?為G的部分L－強(qiáng)邊染色，令S＝｛v0｝.利用貪心算法對(duì)滿足dS（e）≥0的邊進(jìn)行部分L－強(qiáng)邊染色.此時(shí)｜L′（e1）｜≥1，｜L′（e2）｜≥1，由于已著色，下面根據(jù)fi著色的色類可分為2，3，4這3類：

情形1 當(dāng)｜?（fi）｜≤3，此時(shí)｜L′（e1）｜≥2，｜L′（e2）｜≥2，則e1e2可正常著色，從而?擴(kuò)展到G.

情形2 當(dāng)｜?（fi）｜＝4，此時(shí)｜L′（e1）｜≥1，｜L′（e2）｜≥1，考慮邊g1g2的著色.

情形2.1 當(dāng)?（g1）＝?（g2），此時(shí)｜L′（e1）｜≥2，｜L′（e2）｜≥2，則e1e2可正常著色.

情形2.2 當(dāng)?（g1）＝?（f3）或?（g1）＝?（f4）或?（g2）＝?（f3）或?（g2）＝?（f4），此時(shí)｜L′（e1）｜≥2，｜L′（e2）｜≥2，則e1e2可正常著色.

情形2.3 當(dāng)?（g1）≠?（g2）且?（g1）≠?（f3）且?（g1）≠?（f4），不妨設(shè)?（f1）＝a，?（f2）＝b，?（f3）＝c，?（f4）＝d，?（g1）＝x，?（g2）＝y(tǒng)，?（g3）＝z，?（g4）＝m，L1＝｛a，b，c，d，x，y），L2＝｛a，b，c，d，z，m｝.

情形2.3.1 若｜L（e1）∩L1｜≤5或｜L（e2）∩L2｜≤5，則e1e2可正常著色.

情形2.3.2 若｜L（e1）∩L1｜＝6且｜L（e2）∩L2｜＝6，不妨令L（e1）＝｛a，b，c，d，x，y，A｝，L（e2）＝｛a，b，c，d，z，m，B｝.

情形2.3.2.1 若A≠B，令?（e1）＝A，?（e2）＝B，則e1e2可正常著色.

情形2.3.2.2 若A＝B，則對(duì)g1進(jìn)行換色.由于｜L′（g1）｜≥3，對(duì)g1而言，除色x外，還有另外2種色α，β可選，如將?（g1）＝x換為?（g1）＝α.若α≠?（f1）＝a且α≠?（f2）＝b，則可令?（e1）＝e，?（e2）＝A即可完成著色.若α＝?（f1）＝a且α＝?（f2）＝b，則f1隨之換色，令?（f1）＝a，此時(shí)可令?（e1）＝A，?（e2）＝a即可完成著色.

［1］ FAUDREE R J，SCHELP R H，GYARFAS A，et al.The Strong Chromatic Index of Graphs［J］.Ars Combinatoria，1990，29B：205－211.

［2］ WU Jian－zhuan.The Strong Chromatic Index of a Class of Graphs［J］.Discrete Mathematics，2008，308：6 254－6 261.

［3］ 朱海洋.Delta（G）＝3的圖的列表強(qiáng)邊染色［J］.山東理工大學(xué)學(xué)報(bào)，2008，22：54－58.

［4］ ERDOS P.Problems and Results in Combinatorial Analysis and Graph Theory［J］.Discrete Mathematics，1988，72：81－92.

List Strong Edge Coloring of Some Graphs

HUANG Hui－yun
（Nanjing Colleng of Chemical Technology，Nanjing 210048，China）

List strong edge coloring is defined.It is proved that if G is a graph with d（x）＋d（y）≤5，then

coloring；strong edge coloring；strong edge chromatic number；list strong edge coloring；strong edge choice number

book=25,ebook=129

O157.5

A

10.3969／j.issn.1007－2985.2012.04.006

（責(zé)任編輯 向陽(yáng)潔）

1007－2985（2012）04－0025－06

2012－04－11

黃會(huì)蕓（1979－），女，江西高安人，南京化工職業(yè)技術(shù)學(xué)院基礎(chǔ)部講師，碩士，主要從事數(shù)學(xué)教學(xué)研究.