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

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

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

·兰132·                   

州理工大学学

报               第38卷

形3,也可类似于命题2中情形2的证明过程证得:对点染色来说,对边Cn中不存在长为3的2色路.染色来说,又由于Cn中不存在长为4的2色路.故可得对点染色来说,v=0.Wn+1中不存在长f(0)

…,为3的2路.中的边对应色S={vvi=1,2,n}|0i

…,且每种颜色仅用一次,而Wn+1中长集合{1,2,n}为4的路可分为三类:不含S中的边;只含一条S中的边;只含两条S中的边;但无论是哪一类,根据上式的染色,对边染色来说,Wn+1中都不存在长为4的2色路.由引理2知,的一个星n≥6)f为Wn+1(边星-全染色.

综上,命题3成立.

()命题4 设F阶扇,则有+1n≥2n+1为n

T

(n+1)=n+1ssFχ

vv=0  f(vv=0  f(12)n-1n)

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

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

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

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

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

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

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

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

vv=1vv=2vv=3 f( f(f(0n-1)01)0n)(…,)vv=i+2i=2,3,n-2. f(0i)(),情形3构造一个从2mod3V(F 若n≡ ∪n+1)…,到{的映射f如下:E(F0,1,2,n}n+1)

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

(),若imod3v=2;≡2 f(i)(),(…,若imod3v=3i=1,2,n).≡0 f(i)vv=3  f(vv=0  f(vv=0f(12)23)n-1n)}{,}vv1,2,3vv  f(∈{\f(f(ii+1)i)i+1)…,)i=3,4,n-2    (

  证明 记

…,V(Fvvvv={n1)0,1,2,n}+

…,E(Fvvi=1,2,n}∪={n1)0i|+

…,}vvi=1,2,n-1    {ii1|+

由于F根据引理n+1的唯一的最大度顶点是n度的,

T

(n+1)知χ2,n+1.≥ssF

)当n=2时,有F2+1=K3,易得1

T

(2+1)=3ssFχ

)当n=3时,用4种颜色0,1,2,3如下式对  2

F3+1进行染色.

v=0  f(v=1  f(v=2  f(0)1)2)v=1vv=3vv=1 f( f(f(3)01)02)vv=2vv=0f(vv=3 f(f(03)12)23)

易验证f为F3+1的一个星边星-全染色.

)当n=4时,用5种颜色0,31,2,3,4按下式对F4+1进行染色.

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

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

在F对情形1和情vvvvn+1中取路Pn=123…n,形3,在命题1的证明过程中已证,对情形2,也可类似于命题1的证明过程证得:对点染色来说,Pn中不存在长为3的2色路.对边染色来说,Pn中不存在长为4的2色路.由于f(故Fv=0,0)n+1中对点染色来说不存在长为3的2色路.S={vvi=1,|0i…,…,中的边对应色集合为{且每种颜2,n}1,2,n}

色仅用一次,而F不n+1中长为4的路可分为3类:含S中的边;只含一条S中的边;只含两条S中的边;但无论是哪一类,根据上式的染色,对边染色来由引理2知,说,Ffn+1中都不存在长为4的2色路.)为F的一个星边星-全染色.n≥5n+1(

综上,命题4成立.

)命题5 设Kn表示n(阶完全图,则有n≥3

T

)当n=3时,()χ()3.1ssK3=TK3=χT)当n=4时,()χ()5.2ssK4=TK4=χT)当n≥5时,(n)(n),有χ且3≠ssKTKχ

)(T

()n+1≤χKn≤ss

2

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

vv=2vv=3vv=4 f( f(f(02)03)04)vv=0f(vv=4vv=2 f(f(12)23)34)易验证在该染色下,对边染色来说,F4+1中存在长为但不存在长为4的2色路,4的2色圈vvvvv02340,

对点染色来说,也不存在长为3的2色路.这符合星边星-全染色的定义,这样得到f为F4+1的一个星边星-全染色.

)当n≥5时,分3种情形.4

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

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

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

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

上一页第4页

你可能喜欢

热门文档

相关文档

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