Randomly coloring constant degree graphs

DOI10.1002/RSA.20451zbMath1272.05045OpenAlexW1977321916WikidataQ56323813 ScholiaQ56323813MaRDI QIDQ2852546

Eric Vigoda, Martin Dyer, Thomas P. Hayes, Alan M. Frieze

Publication date: 9 October 2013

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://figshare.com/articles/journal_contribution/Randomly_coloring_constant_degree_graphs/6479279

zbMATH Keywords

Glauber dynamicscoupling techniquerandom colorings

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Vertex degrees (05C07)

Related Items (21)

Reconstruction of random colourings ⋮ Randomly coloring planar graphs with fewer colors than the maximum degree ⋮ Coupling with the stationary distribution and improved sampling for colorings and independent sets ⋮ An FPTAS for the hardcore model on random regular bipartite graphs ⋮ On Sampling Simple Paths in Planar Graphs According to Their Lengths ⋮ Perfect sampling from spatial mixing ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model ⋮ Counting Independent Sets and Colorings on Random Regular Bipartite Graphs ⋮ Glauber dynamics on trees: Boundary conditions and mixing time ⋮ Reconstruction for the Potts model ⋮ Rapid mixing of Gibbs sampling on graphs that are sparse on average ⋮ Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models ⋮ Gibbs rapidly samples colorings of \(G(n, d/n)\) ⋮ Counting Hypergraph Colorings in the Local Lemma Regime ⋮ Approximate Counting via Correlation Decay in Spin Systems ⋮ Local uniformity properties for glauber dynamics on graph colorings ⋮ Randomly coloring constant degree graphs ⋮ A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold ⋮ Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs

Cites Work

• Unnamed Item
• Random generation of combinatorial structures from a uniform distribution
• Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
• Percolation and the hard-core lattice gas model
• Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
• A general lower bound for mixing of single-site dynamics on graphs
• Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
• Improved bounds for sampling colorings
• Randomly coloring constant degree graphs
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Adaptive simulated annealing: A near-optimal connection between sampling and counting
• Randomly coloring planar graphs with fewer colors than the maximum degree
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Random walks and anO*(n5) volume algorithm for convex bodies
• Randomly coloring graphs with lower bounds on girth and maximum degree
• The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Fast mixing for independent sets, colorings, and other models on trees
• Variable length path coupling
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs

This page was built for publication: Randomly coloring constant degree graphs