图的星边染色

图的星边染色

论文摘要

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

论文目录

  • 摘要
  • Abstract
  • 前言
  • 1 星边染色概念及性质
  • 2 树的星边染色
  • 3 超立方体的星边染色
  • 4 极大外平面图和极大平面图的星边染色
  • 5 一般图星边色数的上界
  • 参考文献
  • 致谢
  • 相关论文文献

    标签:;  ;  ;  

    图的星边染色
    下载Doc文档

    猜你喜欢