Kempe变换理论研究进展  

Research Progress on the Theory of Kempe Changes

作　　者：许进[1] 刘小青[2] 

机构地区：[1]北京大学信息科学技术学院,北京100871 [2]北京大学高可信软件技术教育部重点实验室,北京100871

出　　处：《电子与信息学报》2017年第6期1493-1502,共10页Journal of Electronics & Information Technology

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

摘　　要：给定一个图G及它的一个正常顶点着色f,G中所有着两种颜色之一的顶点构成的顶点子集导出的子图称为G的一个2-色导出子图,该2-色导出子图的分支称为G的一个2-色分支。Kempe变换是指将图G的某个2-色分支实施颜色互换。自1879年Kempe引入Kempe变换用于证明四色猜想至今,众多学者从不同的角度对Kempe变换展开了研究。该文总结了Kempe变换的一些基本性质;对已有的一些重要成果进行了较为详细的综述;针对Meyniel定理,即每个平面图的所有5-着色构成一个Kempe等价类,给出了一个新而简短的证明方法;提出了一个与着色类型相关的问题,意在探索不同Kempe等价类之间的关系,以加深Kempe变换的研究。Given a graph G and a proper vertex coloring of G , a 2-coloring induced subgraph of G is a subgraph induced by all the vertices with one of two colors, a component of a 2-coloring induced subgraph is called a 2-coloring component. To make a Kempe change is to obtain one coloring from another by exchanging the colors of vertices in a 2-coloring component. Since Kempe introduced Kempe changes in his false proof of the Four Color Theorem in 1879, many scholars devote to the research on Kempe changes from different points of view. The main contributions in this paper are as follows： （1） Some basic properties of Kempe changes are summarized; （2） A series of important results with regard to Kempe changes are to be reviewed and analyzed in detail; （3） Another novel and more brief proof method of Meyniel Theorem, that all 5-colorings of a planar graph are Kempe equivalent, is given out; （4） A problem related with types of colorings is proposed here, which intends to explore the relationships between different Kempe equivalent classes, and thus contributes to the further study.

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

分 类 号：O157.5[理学—数学]