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

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

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

第38卷第1期2012年2月兰 州 理 工 大 学 学 报

JournalofLanzhouUniversitofTechnolo    ygy Vol.38No.1

Feb.2012

()16735196201201012907  文章编号:---

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

刘信生,孙春虎,王志强

()西北师范大学数学与信息科学学院,30070 甘肃兰州 7

摘要:提出图的星边星-全染色的概念,图G的一个正常全染色被称为星边星-全染色,如果对G中点进行星染色,

T

()用构造染色的方法给出一些特殊图(边进行星边染色.并定义图的星边星-全色数,记为χ路,圈,轮,扇,完ssG.

全图)的星边星-全色数.同时运用概率方法给出满足一定条件的图G的星边星-全色数的一个上界,即若图G的

T

()2

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

2?.则χ最大度Δ(G)0,4(≥3Δ-1ssG≤

关键词:星边星-全染色;星边星-全色数;概率方法;Lovász局部引理中图分类号:O157.5  文献标识码:A

Anuerboundofstaredestartotalchromaticnumberofrahs    --     ppggp

,LIU XinshenSUNChunhu,WANGZhiian  qgg---

(,N,)ColleeofMathematicsandInformationScienceorthwestNormalUniversitLanzhou30070,China        7gy

:AAbstractconcetofstaredestartotalcolorinofrahswasresented.Aroertotalcolorinofa            pgggppppg  --

Gwouldbecalledstaredestartotalcolorinifitsverticeswerestarcolorinanditsedeswererah              gggggp  --

T

()edecolorin.ThestaredestartotalchromaticnumberofG wasdefinedanddenotedbstar           gggyχ---ssG.,w,Thestaredestartotalchromaticnumberofsomearticularrahs(ath,ccleheelfan,comlete        gpgppyp--

)w,rahereivenbusinthemethodofcolorinconstruction.Meantimeanuerboundofstarede         gpgyggppg   --,startotalchromaticnumberofrahwhichsatisfieddefiniteconditionswasivenbmeansofrobabilis             gpgpy -

T2?,()2

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

ticmethodnamel4(forarahGifitsmaximumdereeΔ(G)0. Δ-1      ≥3yχgpgssG≤

:;;;Kewordsrobabilisticstaredestartotalcolorinstaredestartotalchromaticnumbermethod      pgggy ----

Lovászlocallemma  

而  图的染色问题不仅是图论的经典问题之一,且在现实生活中有着广泛的应用.1973年,图G的星染色Grünbaum首先提出星染色的概念,

满足G中无长为3的路是G的一个正常顶点染色,

是2-染色的,使得G有星染色的最小颜色数称为G

[]

(的星色数,记为χG).2004年,Fertin等1证明s

扇,完全图)的星边星-全色数,并用概率方法给出满足一定条件的图的星边星-全色数的一个上界.其它

]38-

用概率方法得到图的某种色数的例子[.

[1]

定义1的一个kV,E) 图G(-正常点染色f

被称为G的k若G中没有长为3的路是-星染色,()i简记为k且称χ2-染色的.SVC,n{kG存-|sG=m在k为G的星色数.VC}-S

[2]

定义2的一个kV,E) 图G(-正常边染色f

()

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

并提出星色数的上界能否改进的0Δ2?,sG≤2χ

2]

刘信生等[提出星边染色的概念.使问题.2006年,得G有星边染色的最小颜色数称为星边色数,记作并证明若图G的最大度Δ(则′G).G)≥7,s(χ

2?(′G)

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

≤16Δ-1s(χ本文用构造染色的方法给出一些特殊图(路,圈,轮,

20110331  收稿日期:--

:(,基金项目国家自然科学基金甘肃省教61163054,61163037)  

)育厅基金(050103-

,男,河南光山人,教授.1956  作者简介:刘信生(-)

被称为G的k若G中没有长为4的路是-星边染色,

()i简记为k且称χ2-边染色的.SEC,′n{kG-|sG=m存在k为G的星边色数.EC}-S

根据以上两个概念,自然地提出星边星-全染色

]913-

的概念[.

定义3 图G(的一个kV,E)-正常全染色f被称为G的k若对G中点进行星染-星边星-全染色,

边进行星边染色.简记为k且称色,EST,-S

第1页

你可能喜欢

热门文档

相关文档

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