Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors

DOI10.1007/978-3-642-35261-4_6zbMath1260.05061MaRDI QIDQ4909519

Hsueh-I Lu, Ching-Chen Kuo

Publication date: 21 March 2013

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-35261-4_6

zbMATH Keywords

Markov chain; Glauber dynamics; mixing time; graph colorings

Mathematics Subject Classification ID

60J22: Computational methods in Markov chains

68Q25: Analysis of algorithms and problem complexity

05C15: Coloring of graphs and hypergraphs