提出图的星边星-全染色的概念,图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)
图的星边星-全色数的一个上界_数学_自然科学_专业资料。提出图的星边星-全染色的概念,图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邻点星边色数的一个上界,其中...
热门文档