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

doi:10.11999/JEIT160716

CORC > 北京大学 > 信息科学技术学院

	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).