Strong spatial mixing of list coloring of graphs

DOI10.1002/rsa.20518zbMath1317.05054arXiv1207.1223OpenAlexW2079675572MaRDI QIDQ5265338

No author found.

Publication date: 23 July 2015

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

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

zbMATH Keywords

graph coloringcorrelation decay

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (9)

The topological strong spatial mixing property and new conditions for pressure approximation ⋮ Perfect sampling from spatial mixing ⋮ Correlation decay and the absence of zeros property of partition functions ⋮ Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite \(\Delta \)-regular tree for large \(\Delta \) ⋮ Unnamed Item ⋮ Counting hypergraph matchings up to uniqueness threshold ⋮ Gibbs measures over locally tree-like graphs and percolative entropy over infinite regular trees ⋮ Mixing properties of colourings of the ℤ^d lattice ⋮ Finitary codings for spatial mixing Markov random fields

Cites Work

• Correlation decay and deterministic FPTAS for counting colorings of a graph
• Uniqueness of uniform random colorings of regular trees
• Improved bounds for sampling colorings
• Counting independent sets up to the tree threshold
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• 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
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs

This page was built for publication: Strong spatial mixing of list coloring of graphs