着五色极大平面图的对偶2～3色子图及五色点消减的实验研究

本文对已着五色极大平面图定义了对偶２～３色子图，并将［１］中着四色极大平面图对偶二色子图的两个定理、四个推论推广到此种情况．根据对偶２～３色子图结构属性，作者实现了一个四着色算法．算法要点是，先对图着五色，再轮番对六个三色子图重新着（３或２）色，以消减五色点，直至五色点数为零．本文通过例图说明了这种四着色步骤。

关于极大平面图自同构群的几个定理和生成算法

本文对极大平面图及其若干四着色通过其二色子图间的同构定义了四着色的同构 (定义6、7), 并给出相关定理. 定理A: 若G有同构四着色C1、C2, 置换σ是相应同构置换, 则σ是G的自同构. 定理B: G和其四着色C, 置换σ是其各二色子图共同的自同构, 则σ也是G的自同构.据此, 给出了求解G的自同构群的算法. 一个四连通或五连通的G, 其自同构问题被转化为三对子图的同构、自同构问题.这些子图的连通度通常为2. 点数仍为p, 边数仅为G的三分之一. 对相当广泛的图类,子图可为树或路,使问题的难度大为简化.文中给出两个具体图例. 说明了对数十个点的G, 在普通微机上(如133主频, 16M 内存)