学位论文 > 优秀研究生学位论文题录展示

图的星边染色

作　者: 邓凯
导　师: 刘信生
学　校: 西北师范大学
专　业: 应用数学
关键词: 图正常边染色星边染色概率方法
分类号: O157.5
类　型: 硕士论文
年　份: 2007年
下　载: 50次
引　用: 4次
阅　读: 论文下载

内容摘要

2006年,刘信生等提出了星边染色的概念,若图G的一个正常边染色满足G中没有长为4的路是2-边染色的,则称此染色是G的一个星边染色,使得G有星边染色的最小颜色数称为星边色数,记作χ’_s(G)。本文的主要工作是对图的星边染色做了初步研究,文章分五节。第一节介绍了星边染色的概念及基本性质,给出了路,圈,扇,轮的星边色数,使用了一种方程的方法确定了几个低阶完全图的星边色数,并给出了一般完全图星边色数的一个界,最后研究了正常边染色与星边染色之间的关系。第二节研究了树的星边染色,证明了对最大度为Δ的树T,存在实数ε(1≤ε≤2)使得χ’_s(T)=εΔ,最后利用树的结果给出了Halin图和单圈图星边色数的上界。第三节研究了超立方体的星边染色,证明了对n(≥3)维超立方体Q_n,有n+1≤χ’_s(Q_n)≤2n-2。第四节研究了极大外平面图和极大平面图的星边染色,并界定了它们的星边色数。第五节利用概率方法给出了一般图星边色数的上界。

图的星边染色

内容摘要

全文目录

相似论文