文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 图的星边星全色数的一个上界
侵权投诉

图的星边星全色数的一个上界

提出图的星边星-全染色的概念,图G的一个正常全染色被称为星边星-全染色,如果对G中点进行星染色,边进行星边染色.并定义图的星边星-全色数,记为χsTs(G).用构造染色的方法给出一些特殊图(路,圈,轮,扇,完全图)的星边星-全色数.同时运用概率方法给出满足一定条件的图G的星边星-全色数的一个上界,即若图G的最大度Δ(G)≥30,则χsTs(G)≤24(Δ-1)3/2.

·1第1期              刘信生等:图的星边星-全色数的一个上界                  31·

vv=2f(1n)

(),构造一个从V(mod3C  情形3 若n≡2 ∪n)}到{的映射f如下:E(C1,2,3,4n)

(),若imod3v=1≡1 f(i)(),若imod3v=2;≡2 f(i)

(),(…,)若imod3v=3i=1,2,n-2.≡0 f(i)v=4  f(v=3  f(vv=2f(n-1)n)n-2n-1)

vv=4 f(01)

vv=3 f(04)vv=3 f(23)vv=2f(15)

vv=1 f(02)

vv=5 f(05)vv=6 f(34)

vv=2f(03)

vv=0f(12)vv=0f(45)

易验证,此时W5+1中对点染色来说,不存在长为3的2色路.对边染色来说,不存在长为4的2色路.这样得到f为W5+1的一个星边星-全染色.

)当n≥6时,分3种情形2

(),情形1构造一个从0mod3V(Wn+1) 若n≡ ∪…,到{的映射f如下:E(Wn+1)0,1,2,n}(),若iv=0.mod3v=1;≡1 f(f(0)i)

(),若imod3v=2;≡2 f(i)

(),(…,若imod3v=3;i=1,2,n).≡0 f(i)vv=0  f(vv=3  f(vv=0f(1n)12)23)

vv=1   f(vv1)=4  f(n-1n)n

}{,}vv1,2,3vv  f(∈{\f(f(ii+1)i)i+1)…,)i=1,2,n-3    (

对情形1,在命vvvv  在Cn中取路Pn=123…n.

对情形2和情形3,也可类题1的证明过程中已证,

似于命题1的证明过程证得:Pn中对点染色来说不存在长为3的2色路.Pn中对边染色来说不存在长为4的2色路.同理可证,三条长为3的路P1=

vv1vvP2=vvv1vP3=vvvv1中对n23,n-1n2,n-2n-1n

点染色来说,也不是2色的.四条长为4的路P4=vvvvvPvvvvvPvvvvvn1234,5=n-1n123,6=n-2n-1n12,

也不是2色Pvvvvv7=n-3n-2n-1n1中对边染色来说,)由引理2知,这样得到f为C的一个星边的.n≥3n(星-全染色.所以

vv=2vv=0 f(f(34)45)

}{,}vv1,2,3vv  f(∈{\f(f(ii+1)i)i+1)…,)i=5,6,n-1    (

vv=2vv=4 f( f(01)02)

vv=1f(03)

vv=5vv=3 f(f(04)05)

(…,vv=ii=6,7,n)  f(0i)

(),情形2构造一个从1mod3V(Wn+1) 若n≡ ∪…,到{的映射f如下:E(Wn+1)0,1,2,n}

(),若iv=0.mod3v=1;≡1 f(f(0)i)

(),若imod3v=2;≡2 f(i)

(),(…,)若imod3v=3;i=1,2,n-1.≡0 f(i)

C=n)χ(

T

ss

{()3若n≡0mod3 

()4若n≡1,2mod3 

综上,命题2成立.

),命题3 对n+1阶轮Wn+1(有n≥3

T

)当3≤()n+2;1n≤5时,ssWn+1=χ

T

)当n≥6时,()n+1.2ssWn+1=χ

v=2vv=0vv=1      f(f(f(n)n-2n-1)n-1n)

vv=0f(vv=3vv=0 f(f(1n)12)23)}{,}vv1,2,3vv  f(∈{\f(f(ii+1)i)i+1)

…,)i=3,4,n-3      (

…,,证明 记V(Wn+1)={vvvv0,1,2,n}

…,E(Wn+1)={vvi=1,2,n}vvi=1,2,|∪{|0iii+1…,}n-1vv.∪{1n}

因为Wn+1的轮心是唯一的最大度(为n)顶点,

T

()n+1.所以由引理2知,ssWn+1≥χ

)当n=3时,有W3+1=K4,易得1

TT

(+1)()χ()5=χssW3ssK4=TK4=χ

 当n=4时,

v=0  f(v=1  f(v=f(v=3  f(0)1)2)4)

vv=1vv=2vv=3 f( f(f(02)01)0n)

(…,)vv=i+1i=3,4,n-1.  f(0i)

(),情形3构造一个从2mod3V(Wn+1) 若n≡ ∪…,到{的映射f如下:E(Wn+1)0,1,2,n}

v=0  f(v=4  f(v=3f(0)1)2)

(),若imod3v=1;≡0 f(i)

(),若imod3v=2;≡1 f(i)

),(…,若imod3v=3i=3,4,n).≡2( f(i)

}{,}vv1,2,3vv  f(∈{\f(f(ii+1)i)i+1)…,)i=4,5,n-1     (

vv=0  f(vv=6  f(vv=2  f(1n)12)23)vv=0vv=1vv=2 f(f(f(34)01)0n)

v=4vv=3vv=2 f( f(f(3)01)02)

vv=1vv=4vv=4 f( f(f(03)04)12)vv=0f(vv=5vv=2 f(f(23)34)14)

易验证,此时W4+1中对点染色来说,不存在长为3的2色路.对边染色来说,不存在长为4的2色路.这样得到f为W4+1的一个星边星-全染色.

当n=5时,

vv=5vv=3vv=4 f( f(f(02)03)04)

(…,)vv=i+1i=5,6,n-1  f(0i)对情形1,在vvvvv1.  在Wn+1中取圈Cn=123…n

命题2中情形1的证明过程中已证,对情形2和情

v=0   f(v=3   f(v=2  f(0)1)2)

v=1v=4v=1  f(f(f(3)4)5)

上一页第3页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email