Kempe变换理论研究进展

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

作者：许进, 刘小青

摘要：给定一个图G及它的一个正常顶点着色f, G中所有着两种颜色之一的顶点构成的顶点子集导出的子图称为G的一个2-色导出子图，该2-色导出子图的分支称为G的一个2-色分支。Kempe变换是指将图G的某个2-色分支实施颜色互换。自从1879年KEMPE引入Kempe变换用于证明四色猜想至今，有众多学者从不同的角度对Kempe变换展开了研究。该文总结了Kempe变换的一些基本性质；对已有的一些重要成果进行了较为详细的综述；针对MEYNIEL定理，即每个平面图的所有5-着色构成一个Kempe等价类，给出了一个新的更加简短的证明方法；提出了一个与着色类型相关的问题，意在探索不同Kempe等价类之间的关系，以助于Kempe变换的进一步研究。

关键词：Kempe变换, Kempe等价的, Kempe等价类, 树着色, 圈着色

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