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

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

提出图的星边星-全染色的概念,图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(

上一页第2页

你可能喜欢

热门文档

相关文档

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