提出图的星边星-全染色的概念,图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)
图的星边星-全色数的一个上界_数学_自然科学_专业资料。提出图的星边星-全染色的概念,图G的一个正常全染色被称为星边星-全染色,如果对G中点进行星染色,...
图的点可区别星边色数的一个上界_专业资料。图G的点可区别星边边色数,记为X'vds(G),是图G的点可区别星边染色所用色的最小数目.得到了一些特殊图的星...
( Natural Science) Jan. , 2013 Vol. 36, 1 No. 图的星边色数的一个新的上界 1, 2 2 莫明忠 , 王大飞 ( 1. 柳州师范高等专科学校 数学与计算机...
图的点可区别无圈边色数的一个上界_专业资料。图G的一个正常边染色f,若... 1人阅读 5页 2.00 图的星边星-全色数的一个... 153人阅读 7页 ...
图的邻点可区别Ⅵ-全色数的一个上界_专业资料。根据图的邻点可区别VI-全... 图的点可区别星边色数的... 8人阅读 7页 2.00 若干直积图的邻点...
图的D(2)-点可区别边色数的一个上界_专业资料。用图的概率方法中的赋权... 图的星边星-全色数的一个... 153人阅读 7页 2.00 图的邻点可区别...
平面图线性色数的一个上界_专业资料。如果图G的一个正常染色满足染任意两种... 1人阅读 3页 2.00 图的星边星-全色数的一个... 153人阅读 7页 ...
点可区别边色数的一个上界_专业资料。设G是简单图,f是从V(G)UE(G)到{1,2,…,k}的一个映射.对每个u∈V(G),令C(u)={f(uv)v∈V(G),uv∈E...
21年2 00月第2卷第1 6期 纯粹数 学与 应用 数学 Pur nAppid ahmatc ead leMteis Feb.2010 Vl1 0.NO. 261 图的邻点可 区别全色数 的一个上界 晁福 ...
提出了图的Smarandachely邻点星边染色的概念,讨论了圈、轮、扇的Smarandachely邻点星边染色.并运用概率方法得到了图G的Smarandachely邻点星边色数的一个上界,其中...
热门文档