四色着色的“简化降阶法”  

Simplified Method of Reduction of Order for Four-coloring

作　　者：冯纪先[1] 

机构地区：[1]武汉大学电子信息学院,湖北武汉430072

出　　处：《汕头大学学报（自然科学版）》2008年第4期52-59,共8页Journal of Shantou University：Natural Science Edition

摘　　要：依靠邻接矩阵进行"降阶",分层次地移去3度点和4度点,再借助拓扑结构图进行"升阶、着色",且不加入任何"添加边"而得到平面图的四色着色方案,由此形成平面图着色的"简化降阶法".利用"简化降阶法"对一个一定拓扑结构的12阶最大平面图G_(M12)进行着色,得到G_(M12)的四色着色方案;以同样的方法对一个一定拓扑结构的25阶最大平面图G_(M25)进行着色,得到了G_(M25)的四色着色方案.这两个例子均显示,"简化降阶法"是合理、有效、简便的.In this paper, a ＂simplified method of reduction of order＂ for Four-coloring is presented. A Four-coloring of a maximal planar graph of 12 order GM12 is obtained with ＂simplified method of reduction of order＂ . In the same way, a Four-coloring of a maximal planar graph of 25 order GM25 is obtained with ＂ simplified method of reduction of order＂ Examples show that the ＂ simplified method of reduction of order＂ is valid, feasible and simple.

关 键 词：最大平面图 着色 四色着色方案 “简化降阶法” 

分 类 号：O157.5[理学—数学]