Frozen (Δ + 1)-colourings of bounded degree graphs

DOI10.1017/S0963548320000139zbMath1466.05064arXiv1811.12650MaRDI QIDQ4993126

Guillem Perarnau, Marthe Bonamy, Nicolas Bousquet

Publication date: 15 June 2021

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

random regular graphsGlauber dynamicsisolated vertices\(k\)-recolouring graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Coloring of graphs and hypergraphs (05C15) Vertex degrees (05C07)

Related Items (1)

A polynomial version of Cereceda's conjecture

Cites Work

• Unnamed Item
• Unnamed Item
• Reconfiguration of dominating sets
• On the complexity of reconfiguration problems
• Random generation of combinatorial structures from a uniform distribution
• The asymptotic number of non-negative integer matrices with given row and column sums
• 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
• An FPTAS for Counting Proper Four-Colorings on Cubic Graphs
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Improved Bounds for Randomly Sampling Colorings via Linear Programming
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Kempe equivalence of colourings of cubic graphs

This page was built for publication: Frozen (Δ + 1)-colourings of bounded degree graphs