平面图着色的“移边法”

摘要：

对“n阶最小5度最大平面图”min5GMn及“n阶最小5度平面图”min5Gn的四色着色方案的求解，提出了“移边法”。“移边法”的基本思想是，移去“n阶最小5度最大平面图”min5GMn或“n阶最小5度平面图”min5Gn中的一条二端点均为5度的边，则得到他们各自相应的子图“n阶最小4度平面图”min4Gn。显然，被移去那条边的二个端点，在各自相应的子图中均为4度。这就可以对子图“n阶最小4度平面图”min4Gn，用“降阶法”(即指“移4度点法”)求得子图“n阶最小4度平面图”min4Gn的一个(或多个)四色着色方案。以其中一个四色着色方案为起始，利用“多层次的二色交换法”，即可得到该子图“n阶最小4度平面图”min4Gn的一个相应的“相近四色着色方案集”。在这个“集”中，被移去的边的二个端点是异色的那些四色着色方案，就是原母图“n阶最小5度最大平面图”min5GMn或“n阶最小5度平面图”min5Gn的部分四色着色方案。由此，原母图的四色着色方案就被求得，这就是“移边法”。文中以实例(“Heawood的反例，HCE”GM25.HCE)验证了该方法的正确性和有效性;并得到了“Heawood的反例”的一些四色着色方案(计84种)。

关键词： 平面图 着色方法 降阶法 Heawood反例

作者: 冯纪先

作者单位: 武汉大学电子信息学院 武汉 430072

会议类型: 国内会议

会议名称: 中国电子学会电路与系统学会第二十二届年会

会议地点: 上海

会议语种:中文

页码: 110-115

在线出版日期: 2010-10-01（万方平台首次上网日期，不代表论文的发表时间）