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

发布时间：2018-06-02 22:09

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

【摘要】：给定一个图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等价的。
[Abstract]:Given a graph G and a vertex derived subgraph of any two colors in its normal vertex coloring fG is 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. If the two coloring can reach each other by several Kempe transformations, then the coloring is Kempe equivalent. Mohar conjectures that for any connected kregular graph G when k33, if G is not a complete graph, Then all k-coloring of G is Kempe equivalent. Feghali et al. Solved the case of k = 3. When k34, this conjecture has not been solved. In this paper, we study the case of k = 4 and prove that if G is a 4-regular graph with connectivity less than 3, then all 4-coloring of G is Kempe equivalent) if G is a 4-regular graph and contains a subgraph which is isomorphic to a 4- ring or nearly 5-order complete graph. Then all 4-coloring of G is Kempe equivalent) if G is a 3-connected 4-regular graph, and G has a vertex x and a 4-coloring f, it satisfies that there are three or four vertices in the neighborhood of x with the same color under f. Then all the 4-coloring of G is Kempe equivalent.
【作者单位】：北京大学信息科学技术学院;北京大学高可信软件技术教育部重点实验室;
【基金】：国家973计划项目(2013CB329600) 国家自然科学基金(61372191,61472012,61472433,61572046,61502012,61572492,61572153,61402437)~~
【分类号】：O157.5

【相似文献】