董秀芳

【摘要】 圖的染色問題是圖論研究中的重要問題之一，圖的星邊染色不僅對研究星染色有重要的意義，同時有重要的理論價值和應(yīng)用背景，本文主要研究了聯(lián)圖Pm∨Pn的星邊染色，并給出了它的染色方法以及星邊色數(shù).

【關(guān)鍵詞】 星邊染色;星邊色數(shù);聯(lián)圖

定義1[1] ?設(shè)簡單G，H圖，有V（G）∩V（H）=，E（G）∩E（H）=，若滿足V（G∨H）=V（G）∪V（H），E（G∨（H）=E（G）∪E（H）∪{uv|u∈V（G），v∈V（H）}，則稱G∨H為G與H的聯(lián)圖.

引理1[1] ?設(shè)G是一個圖，Δ（G）=Δ表示G的最大度，則Δ≤χs′（G）≤1+|E（G）|-|M|其中M是G的一個最大匹配.

引理2[1] ?設(shè)G，H是圖，則χs′（G∨H）≤max{χs′（G）.χs′（H）}+p，其中p是G與H之間的連邊數(shù).

定理1 ?χs′（Pn∨P2）= 5，n=2， ?3n-1 2 +4，n≥3且為奇數(shù)， ?3n 2 +3，n≥4且為偶數(shù).

證明 ?情況1：當(dāng)n=2時，P2∨P2是4階完全圖，此時不妨令

f（u1u2）=f（v1v2）=1，f（u1v1）=2，f（u2v2）=3，f（u1v2）=4及f（u2v1）=5，

故易得χs′（P2∨P2）=5.

情況2：當(dāng)n≥3且為奇數(shù)時，對于Pn∨P2來說，有最大匹配M且|M|= n-1 2 +1，

由引理1可得n+1≤χs′（Pn∨P2）≤ 5n+1 2 ，為了證明χs′（Pn∨P2）= 3n-1 2 +4.

不妨先構(gòu)造Pn∨P2的一個星邊染色f：用1染路Pn+2′=v1u1u2…unv2;用2，3循環(huán)地染上其余的邊;用4染邊v1v2;用5，6… n-1 2 +3分別染兩兩匹配中的邊：u2v1與un-1v2，u3v1與un-2v2，…，u n-1 2 v1與u n-3 2 v2; n-1 2 +4，…， 3n-1 2 +4用分別染Pn∨P2中其余的n+1條邊.

下面說明，在正常邊染色的情況下，用 3n-1 2 +3種色會出現(xiàn)長為4的路2-邊染色的.

若f（v1v2）=2，則會出現(xiàn)f（v1u1）=1，f（u1u2）=2，f（u2u3）=1，或f（u3u2）=2，f（u2v1）=5，f（v2vn-1）=5，無論哪種情況都會出現(xiàn)長為4的路是2-邊染色的.相似地，若f（v1v2）=3，也會產(chǎn)生長為4的路是2-邊染色的.

若在最后所余的n+1條邊中用顏色q? n-1 2 +4≤q≤ 3n-1 2 +4 來染其中的某兩邊

uiv2與ujv1（i=1，2，…， n-1 2 ;j= n+3 2 ，…，n），不失一般性，

會出現(xiàn)f（uiv2）=f（ujv1）=q，f（uiv1）=f（un-i+1v2）=i+3仍產(chǎn)生了長為4的路是2-邊染色的所以，當(dāng)n≥3且為奇數(shù)時，有χs′（Pn∨P2）= 3n-1 2 +4.

情況3：當(dāng)n≥4且為偶數(shù)時，對于Pn∨P2有完美匹配M且|M|= n 2 +1，

由引理1知，n+1≤χs′（Pn∨P2）≤ 5n 2 ，為了證明χs′（Pn∨ P2）= 3n 2 +3，先構(gòu)造Pn∨P2的一個星邊染色f：用1染路P′n+2=v1u1u2…unv2上完美匹配中的邊;用2，3循環(huán)地染Pn+2′上其余的邊;用4染邊v1v2;用5，6，…， n 2 +3分別染兩兩匹配中的邊;u2v1與un-1v2，u3v1與un-2v2，…，u n 2 v1與u n 2 +1v2; n 2 +4，…， 3n 2 +4用分別染Pn∨P2中其余的n條邊.

與當(dāng)n為奇數(shù)時的方法相同，在正常邊染色的情況下，若用 3n 2 +2種色進(jìn)行邊染色也會出現(xiàn)長為4的路是2-邊染色的.因此，當(dāng)且為偶數(shù)時，有χs′（Pn∨P2）= 3n 2 +3.

定理2 ?當(dāng)n=3時，χs′（P3∨P3）=10;當(dāng)n≥4時χs′（Pn∨Pn）<n2-3n+9.

證明 ?情況1：當(dāng)n=3時，

令f（u1u2）=f（v1v2）=1，f（u2u3）=f（v2v3）=2，f（u1v1）=f（u3v3）=3，f（u2v2）=4，f（u1v2）=5，f（u1v3）=6，

f（u2v1）=57，f（u2v3）=8，f（u3v1）=9，f（u3v2）=10.

不難驗(yàn)證，此染色為星邊染色且所用邊數(shù)最少，故有χs′（P3∨P3）=9.

情況2：當(dāng)n≥4時，由引理2可得χs′（Pn∨Pn）<χs′（Pn）+n2.

為了證明χs′（Pn∨Pn）<n2-3n+9同樣地先構(gòu)造Pn∨Pn的一個星邊染色f：用1，2，3分別循環(huán)地染Pn兩個中的邊;用4，5循環(huán)地染邊vivi（i=1，2，…，n），用6，7和7，6循環(huán)并交替地染邊u2i-1v2i和u2iv2i-1（i=1，2，…）;用8，9循環(huán)地染邊u2iv2i+1和u2i+1v2i（i=1，2，…）;另外，我們在所余的邊中至少可以找到一對兩兩匹配的邊如u1vi與unvj（i，j=1，2，…，n且i≠j），它們總可以用2或3進(jìn)行染色，這樣一來，對Pn∨Pn中剩余的n（n-3）條邊再各染一種新顏色，此染法保證了在正常邊染色的情況下，沒有出現(xiàn)長為4的路是2-邊染色的，故有χs′（Pn∨Pn）<n2-3n+9.

需進(jìn)一步說明的是：證明過程中也給出了一種較為簡單易行的染色方法.

【參考文獻(xiàn)】

[1]劉信生，鄧凱.最大度不小于7的圖的星邊色數(shù)的 一個上界[J].蘭州大學(xué)學(xué)報：自然科學(xué)版，2008（2）：98-99.

[2]張忠輔，劉林忠.圖的強(qiáng)染色[J].西北師范大學(xué)學(xué)報：自然科學(xué)版，2002（1）：574-583.

[3]陳祥恩.Pn∨Pn的鄰點(diǎn)可區(qū)別全染色[J].西北師范大學(xué)學(xué)報：自然科學(xué)版，2005（1）：13-15.

[4]侯劍鋒，圖上有限制條件的幾類染色問題的研究[D].濟(jì)南：山東大學(xué)，2009.