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