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

依靠邻接矩阵进行"降阶",分层次地移去3度点和4度点,再借助拓扑结构图进行"升阶、着色",且不加入任何"添加边"而得到平面图的四色着色方案,由此形成平面图着色的"简化降阶法".利用"简化降阶法"对一个一定拓扑结构的12阶最大平面图G_(M12)进行着色,得到G_(M12)的四色着色方案;以同样的方法对一个一定拓扑结构的25阶最大平面图G_(M25)进行着色,得到了G_(M25)的四色着色方案.这两个例子均显示,"简化降阶法"是合理、有效、简便的.

“另一个25阶最大平面图”G′_(M25)的四色着色

利用最大平面图着色的"简化降阶法",对一定拓扑结构的"另一个25阶最大平面图"G′_(M25)进行了着色运作.先逐点"降阶",再逐点"着色、升阶、着色",直至获得G′_(M25)的四色着色方案.由于着色过程中,有些点的着色是可以选择的,在这些点作任意选色后,只是找出其中的二个G′_(M25)的四色着色方案,即"四色着色方案壹"和"四色着色方案贰"(其他的四色着色方案未作求解).然后,在"四色着色方案壹"和"四色着色方案贰"的基础上,利用多层次的"二色交换法",相应地分别求出了G′_(M25)的二个相近四色着色方案集,即"相近四色着色方案集壹"和"相近四色着色方案集贰".在"相近四色着色方案集壹"中,含有72个不同的四色着色方案;在"相近四色着色方案集贰"中,含有156个不同的四色着色方案.文中对这二个相近四色着色方案集进行了分析,得到了有意义的结果.

最大平面图G_M的孪生图G_M^T和对角线变换DT

提出了最大平面图G_M的孪生图G_M^T和"孪生图对"的概念和定义,探讨了"孪生图对"的特性,分析了"孪生图对"的四色着色方案彼此间的关系,并由此形成了最大平面图着色的"对角线变换法".文中以二个实例("正二十面体的平面嵌入图";"Appel和Haken的例子")验证了研究的结果,同时也显示了孪生图G_M^T可被应用的场合及其实用性.