Coloring Random Graphs

DOI10.1103/PhysRevLett.89.268701zbMath1267.05121WikidataQ52026352 ScholiaQ52026352MaRDI QIDQ2837678

Riccardo Zecchina, Roberto Mulet, Martin Weigt, Andrea Pagnani

Publication date: 11 July 2013

Published in: Physical Review Letters (Search for Journal in Brave)

zbMATH Keywords

graph coloring; random graphs; average connectivity; clustering phase

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

05C15: Coloring of graphs and hypergraphs

Related Items

Gibbs states and the set of solutions of random constraint satisfaction problems, Almost all graphs with average degree 4 are 3-colorable, Spines of random constraint satisfaction problems: definition and connection with computational complexity, Properties of atypical graphs from negative complexities, Rigorous inequalities between length and time scales in glassy systems, Why almost all \(k\)-colorable graphs are easy to color, Gibbs measures and phase transitions on sparse random graphs, On the dynamics of the glass transition on Bethe lattices, Pairs of SAT-assignments in random Boolean formulæ, A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings, An efficient local search method for random 3-satisfiability, On the survey-propagation equations in random constraint satisfiability problems