论文部分内容阅读
图的着色问题是图论的重要问题之一，并且在离散数学和组合分析中有着广泛的应用。很多领域所涉及的问题都与图的着色理论相关，例如：排课表问题、排序问题、存储问题等等，都是基于图的着色理论。本文主要研究了低度图的星着色和平面图的强边着色，具体内容如下： 首先，综述了一般图着色概念和研究现状，例如：顶点着色、星着色、边着色、强边着色。 其次，引入星着色、强边着色的定义。 最后，根据一般低度图和平面图的结构，用构造的方法重新调整一些点和边的颜色，找到了一类低度图的星色数，同时证明了一类平面图的边色数满足强边着色猜想。