Randomly coloring planar graphs with fewer colors than the maximum degree

DOI10.1002/rsa.20560zbMath1327.05304arXiv0706.1530OpenAlexW2035895308MaRDI QIDQ3460517

Eric Vigoda, Thomas P. Hayes, Juan Carlos Vera

Publication date: 7 January 2016

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

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

zbMATH Keywords

Markov chainsMarkov chain Monte CarloGlauber dynamicsmixing timerandom samplingapproximate countingrandom colorings\(k\)-coloringsfrozen vertices

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

Related Items

Random Instances of Problems in NP – Algorithms and Statistical Physics, Spectral radius of finite and infinite planar graphs and of graphs of bounded genus, On Sampling Simple Paths in Planar Graphs According to Their Lengths, Phase transition for the mixing time of the Glauber dynamics for coloring regular trees, Unnamed Item, Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model, Randomized algorithms with splitting: Why the classic randomized algorithms do not work and how to make them work, The mixing time of Glauber dynamics for coloring regular trees, The Glauber dynamics for edge‐colorings of trees, Approximate Counting via Correlation Decay in Spin Systems, Spectral radius of finite and infinite planar graphs and of graphs of bounded genus (extended abstract), Randomly coloring constant degree graphs, Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Spectral radius of finite and infinite planar graphs and of graphs of bounded genus
• Reconstruction of random colourings
• Coupling with the stationary distribution and improved sampling for colorings and independent sets
• Comparison theorems for reversible Markov chains
• Uniqueness of uniform random colorings of regular trees
• 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
• Systematic scan for sampling colorings
• Markov Chain Algorithms for Planar Lattice Structures
• Randomly coloring constant degree graphs
• The mixing time of Glauber dynamics for coloring regular trees
• Reconstruction for Colorings on Trees
• The Glauber Dynamics for Colorings of Bounded Degree Trees
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Randomly coloring graphs with lower bounds on girth and maximum degree
• Random sampling of 3‐colorings in ℤ²
• Mixing in time and space for lattice spin systems: A combinatorial view
• 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
• Graph colouring and the probabilistic method
• Gibbs rapidly samples colorings of \(G(n, d/n)\)