许 进



极大平面图的结构与着色理论 (4)-运算与Kempe等价类

许 进*

(北京大学高可信软件技术教育部重点实验室 北京 100871),(北京大学信息科学技术学院 北京 100871)

设是一个-色图，若的所有-着色是Kempe等价的，则称为Kempe图。表征色数的Kempe图特征是一尚待解决难题。该文对极大平面图的Kempe等价性进行了研究，其主要贡献是：(1)发现导致两个4-着色是Kempe等价的关键子图为2-色耳，故对2-色耳的特征进行了深入研究；(2)引入-特征图，清晰地刻画了一个图中所有4-着色之间的关联关系，并深入研究了-特征图的性质；(3)揭示了4-色非Kempe极大平面图的Kempe等价类可分为树型，圈型和循环圈型，并指出这3种类型可同时存在于一个极大平面图的4-着色集中；(4)研究了Kempe极大平面图特征，给出了该类图的多米诺递推构造法，以及两个Kempe极大平面图猜想。

Kempe极大平面图；Kempe变换；-运算；Kempe等价类；-特征图；2-色耳

1 引言

无论是理论上还是应用上，平面图都是一类非常重要的图类。理论方面，著名的4-色猜想，唯一4-色平面图猜想，9-色猜想，及3-色问题等[1]不仅在图论领域，乃至整个数学界都具有重大影响；从应用的角度来讲，平面图理论可直接应用于电路布线[2]，信息科学[3]等领域。

极大平面图是平面图中一类重要的图类，它的每个面的边界均为三角形，故也称为三角剖分图。由于著名的4-色猜想的研究对象可归为极大平面图，因此，100多年来，关于极大平面图的研究吸引了众多学者，他们围绕着4-色猜想，相继研究了度序列，构造，着色特性，可遍历性，生成运算等诸多方面[4]。……