Frozen colourings of bounded degree graphs

DOI10.1016/j.endm.2018.06.029zbMath1397.05058OpenAlexW2884093028MaRDI QIDQ1792087

Guillem Perarnau, Nicolas Bousquet, Marthe Bonamy

Publication date: 11 October 2018

Full work available at URL: http://pure-oai.bham.ac.uk/ws/files/54547447/DMD_frozen.pdf

zbMATH Keywords

Glauber dynamicsgraph colouringsrandom colouringsrecolouring graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex degrees (05C07)

Related Items (2)

Digraph redicolouring ⋮ An update on reconfiguring 10-colorings of planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconfiguration of dominating sets
• Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
• Systematic scan for sampling colorings
• Improved bounds for sampling colorings
• A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
• The complexity of change
• The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

This page was built for publication: Frozen colourings of bounded degree graphs