论文部分内容阅读
在19世纪的英国,奥古斯都.德.摩根(Augustus De Morgan)的学生弗雷德里克.格思里的哥哥弗朗西斯.格思里(Francis guthrie)在对英国地图进行染色时发现,如果共同边界的区域染不同的颜色,只需4种颜色就可以染完整个地图,由此诞生了著名的四色猜想,染色理论研究也由此开始.图染色理论作为一个重要的图论研究方向,一直被学者和专家所研究.其中,特殊图类在图论研究中用来做反例,充当达到条件的极图,因此,研究特殊图的着色具有重要的理论意义和实际应用价值.本文主要研究了几类特殊图(广义皮特森图,广义谢尔宾斯基图,点分裂图)的性质并得到了具体染色数.第一章首先介绍了图论中染色理论和特殊图的发展历程,并简单叙述了Grundy着色和多彩着色的研究现状.然后,对广义皮特森图,广义谢尔宾斯基和点分裂图的构造与意义做了简要的总结.第二章通过研究广义皮特森图的Grundy着色,得到了广义皮特森图的一些性质,由于当n≠2l且l≠1时,广义皮特森图P(n,l)是3正则图,因此我们根据它的结构给出了具体的染色方案,并得到Grundy染色数.第三章研究了几类特殊图的多彩染色,首先通过研究度不超过3的树的平方图的一些性质,得到了度小于3的树的平方图是平面图并且给出具体的构造方案,其次证明了它是完美图,最后考虑了广义谢尔宾斯基图和友谊图的多彩染色及非正常染色,并求出了具体的染色数.第四章研究了路,圈,轮,扇的点分裂图的Grundy染色.点分裂图的构造是对图进行变换的一种方式,在图论的研究中经常被用到.本章通过对特殊图的结构分析,给出了具体的染色方法和染色数.本文中通过构造具体的染色方案求出了有关图的染色数,并通过理论分析证明了构造的合理性.这些研究结果体现了特殊图染色理论的价值,同时我们在一些章节也提出了可以进一步研究的问题.