4-正则图着色的Kempe等价性  

Kempe Equivalence of Colorings of 4-regular Graphs

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

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

出　　处：《电子与信息学报》2017年第5期1233-1244,共12页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-色分支实施颜色互换。若两个着色之间可通过若干次Kempe变换达到对方,则这两个着色是Kempe等价的。Mohar猜想当k33时,对于任意的连通k-正则图G,若G不是完全图,则G的所有k-着色是Kempe等价的。Feghali等人解决了k=3时的情况,当k34时,此猜想尚未解决。该文研究了k=4时的情况,证明了:(1)若G是一个连通度小于3的4-正则图,则G的所有4-着色是Kempe等价的;(2)若G是4-正则图,且含有与4-轮或近5-阶完全图同构的子图,则G的所有4-着色是Kempe等价的;(3)若G是一个3-连通4-正则图,且G存在一个顶点x和一个4-着色f,满足x的邻域中有3个或4个顶点在f下着相同颜色,则G的所有4-着色是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. Two colorings are Kempe equivalent if each one can be obtained from the other by a series of Kempe changes. Mohar conjectured that, for k 〉_ 3, all k-colorings of connected k-regular graphs that are not complete are Kempe equivalent. Feghali et al. addressed the case k --- 3, and it is still an unsolved conjecture for k 〉 4. This paper considers the case k -- 4 by showing that： （1） if G is a connected 4-regular graph that is not 3-connected, then all 4-colorings of G are Kempe equivalent; （2） if G is a connected 4-regular graph that contains an induced subgraph isomorphic to a 4-wheel or a nearly complete graph of order 5, then all 4-colorings of G are Kempe equivalent; （3） if G is a 3-connceted 4-regular graph with a 4-coloring f and a vertex x such that there are three or four neighbors of x colored with the same color under f, then all 4-colorings of G are Kempe equivalent.

关 键 词：Kempe等价 Kempe变换 Kempe等价类 4-正则图 

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