A new Kempe invariant and the (non)-ergodicity of the Wang–Swendsen–Kotecký algorithm

DOI10.1088/1751-8113/42/22/225204MaRDI QIDQ5321801zbMATH OpenOpenAlexWikidataFDO

Authors Bojan Mohar, Jesús Salas

Publication date 15 July 2009

Published in Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0901.1010

zbMATH Keywords

new Kempe invariantnon-ergodicity of the Wang-Swendsen-Kotecky algorithm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Ergodic theory (37A99)

Abstract: We prove that for the class of three-colorable triangulations of a closed oriented surface, the degree of a four-coloring modulo 12 is an invariant under Kempe changes. We use this general result to prove that for all triangulations T(3L,3M) of the torus with 3<= L <= M, there are at least two Kempe equivalence classes. This result implies in particular that the Wang-Swendsen-Kotecky algorithm for the zero-temperature 4-state Potts antiferromagnet on these triangulations T(3L,3M) of the torus is not ergodic.

Recommendations

• Ergodicity of the Wang–Swendsen–Kotecký algorithm on several classes of lattices on the torus
• On a conjecture of Mohar concerning Kempe equivalence of regular graphs
• Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings
• Height representation, critical exponents, and ergodicity in the four-state triangular Potts antiferromagnet
• In most 6-regular toroidal graphs all 5-colorings are Kempe equivalent

Cited in

(19)

• On a conjecture of Mohar concerning Kempe equivalence of regular graphs
• In most 6-regular toroidal graphs all 5-colorings are Kempe equivalent
• Counting edge-Kempe-equivalence classes for 3-edge-colored cubic graphs
• On Vizing's edge colouring question
• Kempe equivalence of edge-colorings in subcubic and subquartic graphs
• The three-state Potts antiferromagnet on plane quadrangulations
• Ergodicity of the Wang–Swendsen–Kotecký algorithm on several classes of lattices on the torus
• Diameter of colorings under Kempe changes
• Kempe equivalence of 4‐critical planar graphs
• Kempe equivalence of almost bipartite graphs
• On a recolouring version of Hadwiger's conjecture
• Worm Monte Carlo study of the honeycomb-lattice loop model
• Kempe changes in degenerate graphs
• Kempe equivalent list colorings revisited
• Kempe classes and almost bipartite graphs
• Kempe equivalence of 4-colorings of graphs on non-orientable surfaces
• Kempe equivalence classes of cubic graphs embedded on the projective plane
• On a recolouring version of Hadwiger's conjecture (extended abstract)
• Coloring reconfiguration under color swapping

This page was built for publication: A new Kempe invariant and the (non)-ergodicity of the Wang–Swendsen–Kotecký algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5321801)