On a conjecture of Mohar concerning Kempe equivalence of regular graphs

DOI10.1016/J.JCTB.2018.08.002zbMath1404.05049arXiv1510.06964OpenAlexW2963390106WikidataQ129370382 ScholiaQ129370382MaRDI QIDQ1719578

Nicolas Bousquet, Matthew Johnson, Marthe Bonamy, Carl Feghali

Publication date: 8 February 2019

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

regular graphsgraph colouringantiferromagnetic Potts modelKempe equivalenceKempe chainWang-Swendsen-Kotecký algorithm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Related Items (16)

A polynomial version of Cereceda's conjecture ⋮ TS-reconfiguration of dominating sets in circle and circular-arc graphs ⋮ In most 6-regular toroidal graphs all 5-colorings are Kempe equivalent ⋮ Switching 3-edge-colorings of cubic graphs ⋮ Kempe equivalence of 4‐critical planar graphs ⋮ On Vizing's edge colouring question ⋮ Kempe equivalent list edge-colorings of planar graphs ⋮ On a recolouring version of Hadwiger's conjecture ⋮ Strengthening a Theorem of Meyniel ⋮ Unnamed Item ⋮ Dominating sets reconfiguration under token sliding ⋮ Kempe equivalence of colourings of cubic graphs ⋮ Diameter of colorings under Kempe changes ⋮ Distributed Recoloring ⋮ Introduction to reconfiguration ⋮ Ergodicity of the Wang–Swendsen–Kotecký algorithm on several classes of lattices on the torus

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding shortest paths between graph colourings
• Perfectly contractile graphs
• Fast recoloring of sparse graphs
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Mixing 3-colourings in bipartite graphs
• Kempe classes and the Hadwiger conjecture
• Geometric coloring theory
• Les 5-colorations d'un graphe planaire forment une classe de commutation unique
• Recoloring graphs via tree decompositions
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Counting edge-Kempe-equivalence classes for 3-edge-colored cubic graphs
• Connectedness of the graph of vertex-colourings
• A Personal List of Unsolved Problems Concerning Lattice Gases and Antiferromagnetic Potts Models
• Improved bounds for sampling colorings
• A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
• The complexity of change
• Kempe Equivalence of Edge-Colorings in Subcubic and Subquartic Graphs
• The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
• Finding paths between 3-colorings
• A new Kempe invariant and the (non)-ergodicity of the Wang–Swendsen–Kotecký algorithm
• New proof of brooks' theorem
• Kempe equivalence of colourings of cubic graphs

This page was built for publication: On a conjecture of Mohar concerning Kempe equivalence of regular graphs