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

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

作者：刘小青, 许进

单位：1.(北京大学信息科学技术学院 北京 100871) ②(北京大学高可信软件技术教育部重点实验室 北京 100871)

摘要：给定一个图G及它的一个正常顶点着色f, G中任意两种颜色的顶点导出子图称为G的一个2-色导出子图，该2-色导出子图的分支称为G的一个2-色分支。Kempe变换是指将图G的某个2-色分支实施颜色互换。若两个着色之间可通过若干次Kempe变换达到对方，则这两个着色是Kempe等价的。Mohar猜想当k3时，对于任意的连通k-正则图G，若G不是完全图，则G的所有k-着色是Kempe等价的。Feghali等人解决了k=3时的情况，当k4时，此猜想尚未解决。该文研究了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等价的。

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

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