Randomly coloring planar graphs with fewer colors than the maximum degree
DOI10.1002/rsa.20560zbMath1327.05304arXiv0706.1530MaRDI 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
Markov chains; Markov chain Monte Carlo; Glauber dynamics; mixing time; random sampling; approximate counting; random colorings; \(k\)-colorings; frozen vertices
05C35: Extremal problems in graph theory
05C80: Random graphs (graph-theoretic aspects)
60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
60J20: Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
05C10: Planar graphs; geometric and topological aspects of graph theory
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C07: Vertex degrees
