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

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