摘要
依靠邻接矩阵进行"降阶",分层次地移去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.
出处
《汕头大学学报（自然科学版）》
2008年第4期52-59,共8页
Journal of Shantou University：Natural Science Edition
关键词
最大平面图
着色
四色着色方案
“简化降阶法”
maximal planar graph
coloring
Four-coloring
＂simplified method of reduction of order＂ .
