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

来源：电子与信息学报杂志2016年第7期北京时间：

作者：许进

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

关键词：Kempe极大平面图, Kempe变换, -运算, Kempe等价类, -特征图, 2-色耳

基金资助：国家973计划项目(2013CB329600)，国家自然科学基金(61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437)