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