Kempe变换理论研究进展

发布时间：2018-05-03 22:17

本文选题：Kempe变换 + Kempe等价类　；参考：《电子与信息学报》2017年06期

【摘要】：给定一个图G及它的一个正常顶点着色f,G中所有着两种颜色之一的顶点构成的顶点子集导出的子图称为G的一个2-色导出子图,该2-色导出子图的分支称为G的一个2-色分支。Kempe变换是指将图G的某个2-色分支实施颜色互换。自1879年Kempe引入Kempe变换用于证明四色猜想至今,众多学者从不同的角度对Kempe变换展开了研究。该文总结了Kempe变换的一些基本性质;对已有的一些重要成果进行了较为详细的综述;针对Meyniel定理,即每个平面图的所有5-着色构成一个Kempe等价类,给出了一个新而简短的证明方法;提出了一个与着色类型相关的问题,意在探索不同Kempe等价类之间的关系,以加深Kempe变换的研究。
[Abstract]:Given a graph G and one of its normal vertex coloring subgraphs, all vertex subgraphs derived from a vertex subset of one of two colors are called a 2-chromatic derived subgraph of G. The branch of the 2-chromatic derived subgraph is called a 2-chromatic branch of G. Kempe transformation means that some 2-chromatic branch of G is interchanged. Since Kempe introduced Kempe transform to prove four-color conjecture in 1879, many scholars have studied Kempe transform from different angles. In this paper, some basic properties of Kempe transformation are summarized, some important achievements are summarized in detail, and for the Meyniel theorem, all 5-coloring of every planar graph constitutes a Kempe equivalence class. In this paper, a new and brief proof method is given, and a problem related to coloring type is presented, which is intended to explore the relationship between different Kempe equivalence classes in order to deepen the study of Kempe transformation.
【作者单位】：北京大学信息科学技术学院;北京大学高可信软件技术教育部重点实验室;
【基金】：国家973计划项目(2013CB329600) 国家自然科学基金(61372191,61472012,61472433,61572046,61502012,61572492,61572153,61402437)~~
【分类号】：O157.5

【相似文献】