提出图的星边星-全染色的概念,图G的一个正常全染色被称为星边星-全染色,如果对G中点进行星染色,边进行星边染色.并定义图的星边星-全色数,记为χsTs(G).用构造染色的方法给出一些特殊图(路,圈,轮,扇,完全图)的星边星-全色数.同时运用概率方法给出满足一定条件的图G的星边星-全色数的一个上界,即若图G的最大度Δ(G)≥30,则χsTs(G)≤24(Δ-1)3/2.
·兰130·
T
()m{ink|G存在kEST}-SssG=χ
为G的星边星-全色数.
州理工大学学
报 第38卷
因此对边染色来说,Pn中不存在长为4的2色路.由引理2知,这样得到f为Pn(的一个星边n≥2)星-全染色.所以
T
(n)=3ssPχ
),则有n≥2 命题2 设n阶圈Cn(
()3,若n≡0mod3 T
()C=nsχs
()4,若n≡1,2mod3
当n=2时,vvv1. 证明 设Cn=v123…vn
T
(2)当n≥3时,分3种情况:=4.ssCχ
引理1 设图G的最大度为Δ,则G的正常全色数χT(G)≥Δ+1.
证明 因为G的最大度为Δ,即与最大度顶点而这Δ条边均染不同颜色,且相关联的边有Δ条,
都与最大度顶点的染色不同.故有()TG≥Δ+1χ
则 引理2 设图G的最大度为Δ,
T
()ssG≥Δ+1χ
因为G的星边星-全染色满足 证明 根据定义,
正常全染色的条件,而G的最大度为Δ,所以由引理1有
T
()ssG≥Δ+1χ
{
(),情形1 若n≡0由引理2知:mod3
T
(n)≥3ssCχ
构造一个从V(到{的映射f如CC1,2,3}∪E(n)n)下:
圈,轮,扇,完全图的星边星-全1 路,染色
T
),(n)命题1 设n阶路Pn(则有χn≥2=3.ssP
,,若i若i≡2(mod3)v=1;mod3)≡1( f(i)
,…,若i≡0(v=2;mod3)v=3(i=1,2, f(f(i)i)
n).
,}(vv1,2,3}vvi=1,∈{\{f(f(f(ii+1)i)i+1)
…,),2,n-1vv=2.f(1n)
()当n≡1,时,可以证明C2mod3 n用3种颜色不可染.
,假设C由于2,3可染.n可用3种颜色1
对CV(CCn,n=E(n=n中任一条边都与其两端点均染不同颜色,故任意取出Cn中的一条边e
,及其两端点,都对应颜色集合{且每种颜色1,2,3},这样一来可对C仅用一次,2,3循环n用三种颜色1染色,设f(用1v=1,vv=3,v=2,32f(f(1)12)2)来表示v同理可知,v12这条边及其两端点的染色.用2v=2,vv=1,v=3,13来表示f(f(f(2)23)3)
如此循环下去,可vv23这条边及其两端点的染色.}得到颜色集合{的一系列循环置换,可表示为1,2,3由于每一个置换对应C132→213→321→132,n中的
而这个循环置换的周期为3,因而得到一条边,
这E(E(CCn≡1,2(modn应为3的倍数,n=
)矛盾.故当n≡1,时,32(mod3)C n用3种颜色不可染.此时分情形2和情形3两种情况:
(),情形2 若n≡1构造一个从V(mod3C ∪n)}到{的映射f如下:E(C1,2,3,4n)
v=1 f(v=2 f(v=3f(1)2)3)
证明 设Pn=v由引理2知,vv123…vn,
T
(n)构造一个从V(到{Pn)Pn)1,2,3}≥3.∪E(ssPχ
的映射f如下:
(),若imod3v=1;≡1 f(i)(),若imod3v=2;≡2 f(i)
(),(…,若imod3v=3i=1,2,n).≡0 f(i)
}{,}vv1,2,3vv\f(f(f(ii1)i)i1)++∈{(…,)i=1,2,n-1
在Pn中任取一条长为3的路
…,)P3=vvvvi=1,2,n-3ii1i2i3(+++根据上式的染色,易知:
vvv=f(f(i)i3)i1)++≠f(
vvf(i)i2)+≠f(
且
vvf(i1)i2)++≠f(
因此对点染色来说,Pn中不存在长为3的2色路.在Pn中任取一条长为4的路
…,)P4=vvvvvi=1,2,n-4ii1i2i3i4 (++++根据上式的染色,易知:
vvvv=f(=f( f(f(i)i3)i1)i4)+++
vvvv f(f(i)i1)i)i2)++≠f(≠f(且从而
v=4 f(vv=3 vv=4f(f(4)12)23)
vv=1vv=2 f(f(34)45)(),若i-4≡1mod3v=1; f(i)
(),若i-4≡2mod3v=2; f(i)
(),…,若i-4≡0mod3v=3(i=5,6,n). f(i)
}{,}vv1,2,3vv\f(f(f(ii1)i)i1)++∈{…,)i=5,6,n-1 (
vvf(i1)i2)++≠f(
vvvvf(ii1)i1i2)+++≠f(
vvvvf(ii1)i2i3)+++≠f(vvvvf(i1i2)i2i3)++++≠f(
图的星边星-全色数的一个上界_数学_自然科学_专业资料。提出图的星边星-全染色的概念,图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邻点星边色数的一个上界,其中...
热门文档