李永艳, 杜 静

(沧州交通学院 通识教育学院, 河北 黄骅 061199)

关于染色问题,国内外许多学者在传统边染色、点染色和全染色基础上,增加相应的条件,提出了新的染色概念.Kalkowski M等[1]介绍了图的邻和可区别一般边染色,Przybylo等[2]进一步提出邻和可区别一般全染色概念,Flandrin等[3]在此基础上提出邻点扩展和可区别全染色,研究了路、圈、完全图、树等图的邻点扩展和可区别全染色,并提出一个猜想.张辉等[4-5]研究了星、扇、双星及联图的邻点扩展和可区别全染色.刘秀丽[6]讨论了Mycielski图的邻点可区别I-全染色,本文研究了路、圈、星、扇、轮的Mycielski图的邻点扩展和可区别全染色.

1 预备知识

定义2[6]对简单图G,若V(M(G))=V(G)∪V′∪{ω},

其中:V′={v′|v∈V(G)},{ω}∩(V∪V′)=∅,称图M(G)是图G的Mycielski图.

命题1[3]设Pm(m≥2)是m阶的路,则

命题2[3]设Cm(m≥3)是m阶的圈,则

egndi∑(Cm)=2

命题3[3]设Kn(n≥2)是n阶的完全图,则

egndi∑(Kn)=2

命题4[3]设T是n(n≥2)阶的树,则

egndi∑(T)≤2

猜想1(NESD猜想)[3]设G为简单图,则

egndi∑(G)≤2

文中未加说明的符号或术语可参见文献[7].

2 主要结果

定理1设Pn表示阶为n(n≥2)的路,则有egndi∑(M(Pn))=2.

证明设V(Pn)={v1,v2,…,vn},E(Pn)={v1v2,v2v3,…,vn-1vn},则

V(M(Pn))={v1,v2,…,vn}∪

{v′1,v′2,…,v′n}∪{ω}

E(M(Pn))={vivi+1|i=1,2,…,n-1}∪

{ωv′i|i=1,2,…,n}∪

{viv′j||i-j|=1,i,j=1,2,…,n}

令f是M(Pn)的一个全k-染色,显然M(Pn)没有NESD全1-染色,下面给出M(Pn)的一个NESD全2-染色.

情形1n=2.此时M(Pn)≅C5,由命题2得

egndi∑(M(P2))=egndi∑(C5)=2

情形2n≥3.此时所有边染颜色1,令f(ω)=1,f(vi)=1,i=1,2,…,n

则w(v′1)=w(v′n)=4,w(v′i)=6,i=2,3,…,n-1,w(v1)=4,

显然,f是M(Pn)的一个NESD全2-染色.

定理2设Cn表示阶为n(n≥3)的圈,则有

egndi∑(M(Cn))=2

证明M(Cn)即在M(Pn)的基础上添加3条边v1vn,v1v′n,v′1vn,

情形1n>3,n≡0(mod 4).此时M(Cn)与M(Pn)染色f相同,则w(v′i)=6,i=1,2,…,n,

显然,f是M(Cn)的一个NESD全2-染色.

情形2n>3,n≡1(mod 4).此时在M(Pn)染色f基础上,将f(vn-1vn)=1改为f(vn-1vn)=2,将f(v′n)=2改为f(v′n)=1 ,则w(v′i)=6,i=1,2,…,n

显然,f是M(Cn)的一个NESD全2-染色.

情形3n>3,n≡2(mod 4).此时M(Cn)与M(Pn)染色f相同,则w(v′i)=6,i=1,2,…,n

显然,f是M(Cn)的一个NESD全2-染色.

情形4n>3,n≡3(mod 4).此时在M(Pn)染色f基础上,将f(v′n-1vn)=1改为f(v′n-1vn)=2,则w(v′i)=6,i=1,2,…,n-2,n,w(v′n-1)=7

显然,f是M(Cn)的一个NESD全2-染色.

情形5n=3.此时设f是M(Cn)的一个全k-染色,令f(v′1)=2,其余点染颜色1,f(ωv′1)=f(v′2v3)=2,其余边染颜色1,……