咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >On a conjecture of Mohar conce... 收藏

On a conjecture of Mohar concerning Kempe equivalence of regular graphs

在上一有关常规图的 Kempe 等价的 Mohar 的 conjecture

作     者:Bonamy, Marthe Bousquet, Nicolas Feghali, Carl Johnson, Matthew 

作者机构:CNRS LaBRI Bordeaux France Univ Grenoble Alpes CNRS G SCOP Grenoble France Univ Bergen Dept Informat Bergen Norway Univ Durham Dept Comp Sci Durham England 

出 版 物:《JOURNAL OF COMBINATORIAL THEORY SERIES B》 (组合理论杂志,B辑)

年 卷 期:2019年第135卷

页      面:179-199页

核心收录:

学科分类:07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基  金:Research Council of Norway 

主  题:Graph colouring Kempe equivalence Regular graphs Kempe chain Wang-Swendsen-Kotecky algorithm Antiferromagnetic Potts model 

摘      要:Let G be a graph with a vertex colouring alpha. Let a and b be two colours. Then a connected component of the subgraph induced by those vertices coloured either a or b is known as a Kempe chain. A colouring of G obtained from alpha by swapping the colours on the vertices of a Kempe chain is said to have been obtained by a Kempe change. Two colourings of G are Kempe equivalent if one can be obtained from the other by a sequence of Kempe changes. A conjecture of Mohar (2007) asserts that, for k = 3, all k-colourings of a k-regular graph that is not complete are Kempe equivalent. It was later shown that all 3-colourings of a cubic graph that is neither K-4 nor the triangular prism are Kempe equivalent. In this paper, we prove that the conjecture holds for each k = 4. We also report the implications of this result on the validity of the Wang-Swendsen-Kotecky algorithm for the antiferromagnetic Potts model at zero-temperature. (C) 2018 Elsevier Inc. All rights reserved.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分