4-正则图着色的Kempe等价性; Kempe Equivalence of Colorings of 4-regular Graphs | |
刘小青*① ; 许 进①②#x0D | |
刊名 | 电子与信息学报
![]() |
2017 | |
关键词 | Kempe等价 Kempe变换 Kempe等价类 4-正则图 |
DOI | 10.11999/JEIT160716 |
英文摘要 | 给定一个图G 及它的一个正常顶点着色f, G 中任意两种颜色的顶点导出子图称为G 的一个2-色导出子图,该 2-色导出子图的分支称为G 的一个 2-色分支。Kempe 变换是指将图G 的某个 2-色分支实施颜色互换。若两个着色之间可通过若干次Kempe变换达到对方,则这两个着色是Kempe等价的。Mohar猜想当k≥3时,对于任意的连通k-正则图G ,若G 不是完全图,则G 的所有k-着色是Kempe等价的。Feghali等人解决了k =3时的情况,当k≥4时,此猜想尚未解决。该文研究了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等价的。 |
语种 | 英语 |
内容类型 | 期刊论文 |
源URL | [http://ir.pku.edu.cn/handle/20.500.11897/483802] ![]() |
专题 | 信息科学技术学院 |
推荐引用方式 GB/T 7714 | 刘小青*①,许 进①②#x0D. 4-正则图着色的Kempe等价性, Kempe Equivalence of Colorings of 4-regular Graphs[J]. 电子与信息学报,2017. |
APA | 刘小青*①,&许 进①②#x0D.(2017).4-正则图着色的Kempe等价性.电子与信息学报. |
MLA | 刘小青*①,et al."4-正则图着色的Kempe等价性".电子与信息学报 (2017). |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论