Pm∨Pn联图的星边染色

董秀芳

【摘要】 图的染色问题是图论研究中的重要问题之一，图的星边染色不仅对研究星染色有重要的意义，同时有重要的理论价值和应用背景，本文主要研究了联图Pm∨Pn的星边染色，并给出了它的染色方法以及星边色数.

【关键词】 星边染色;星边色数;联图

定义1[1]  设简单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的联图.

引理1[1]  设G是一个图，Δ（G）=Δ表示G的最大度，则Δ≤χs′（G）≤1+|E（G）|-|M|其中M是G的一个最大匹配.

引理2[1]  设G，H是图，则χs′（G∨H）≤max{χs′（G）.χs′（H）}+p，其中p是G与H之间的连边数.

定理1  χs′（Pn∨P2）= 5，n=2，  3n-1 2 +4，n≥3且为奇数，  3n 2 +3，n≥4且为偶数.

证明  情况1：当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：当n≥3且为奇数时，对于Pn∨P2来说，有最大匹配M且|M|= n-1 2 +1，

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

不妨先构造Pn∨P2的一个星边染色f：用1染路Pn+2′=v1u1u2…unv2;用2，3循环地染上其余的边;用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种色会出现长为4的路2-边染色的.

若f（v1v2）=2，则会出现f（v1u1）=1，f（u1u2）=2，f（u2u3）=1，或f（u3u2）=2，f（u2v1）=5，f（v2vn-1）=5，无论哪种情况都会出现长为4的路是2-边染色的.相似地，若f（v1v2）=3，也会产生长为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），不失一般性，

会出现f（uiv2）=f（ujv1）=q，f（uiv1）=f（un-i+1v2）=i+3仍產生了长为4的路是2-边染色的所以，当n≥3且为奇数时，有χs′（Pn∨P2）= 3n-1 2 +4.

情况3：当n≥4且为偶数时，对于Pn∨P2有完美匹配M且|M|= n 2 +1，

由引理1知，n+1≤χs′（Pn∨P2）≤ 5n 2 ，为了证明χs′（Pn∨ P2）= 3n 2 +3，先构造Pn∨P2的一个星边染色f：用1染路P′n+2=v1u1u2…unv2上完美匹配中的边;用2，3循环地染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条边.

与当n为奇数时的方法相同，在正常边染色的情况下，若用 3n 2 +2种色进行边染色也会出现长为4的路是2-边染色的.因此，当且为偶数时，有χs′（Pn∨P2）= 3n 2 +3.

定理2  当n=3时，χs′（P3∨P3）=10;当n≥4时χs′（Pn∨Pn）<n2-3n+9.

证明  情况1：当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.

不难验证，此染色为星边染色且所用边数最少，故有χs′（P3∨P3）=9.

情况2：当n≥4时，由引理2可得χs′（Pn∨Pn）<χs′（Pn）+n2.

为了证明χs′（Pn∨Pn）<n2-3n+9同样地先构造Pn∨Pn的一个星边染色f：用1，2，3分别循环地染Pn两个中的边;用4，5循环地染边vivi（i=1，2，…，n），用6，7和7，6循环并交替地染边u2i-1v2i和u2iv2i-1（i=1，2，…）;用8，9循环地染边u2iv2i+1和u2i+1v2i（i=1，2，…）;另外，我们在所余的边中至少可以找到一对两两匹配的边如u1vi与unvj（i，j=1，2，…，n且i≠j），它们总可以用2或3进行染色，这样一来，对Pn∨Pn中剩余的n（n-3）条边再各染一种新颜色，此染法保证了在正常边染色的情况下，没有出现长为4的路是2-边染色的，故有χs′（Pn∨Pn）<n2-3n+9.

需进一步说明的是：证明过程中也给出了一种较为简单易行的染色方法.

【参考文献】

[1]刘信生，邓凯.最大度不小于7的图的星边色数的 一个上界[J].兰州大学学报：自然科学版，2008（2）：98-99.

[2]张忠辅，刘林忠.图的强染色[J].西北师范大学学报：自然科学版，2002（1）：574-583.

[3]陈祥恩.Pn∨Pn的邻点可区别全染色[J].西北师范大学学报：自然科学版，2005（1）：13-15.

[4]侯剑锋，图上有限制条件的几类染色问题的研究[D].济南：山东大学，2009.