Coloring Random Graphs
From MaRDI portal
Publication:2837678
DOI10.1103/PhysRevLett.89.268701zbMath1267.05121OpenAlexW1854875838WikidataQ52026352 ScholiaQ52026352MaRDI QIDQ2837678
Roberto Mulet, Riccardo Zecchina, Andrea Pagnani, Martin Weigt
Publication date: 11 July 2013
Published in: Physical Review Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1103/physrevlett.89.268701
Related Items
A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings, Properties of atypical graphs from negative complexities, Rigorous inequalities between length and time scales in glassy systems, Upper-bounding the \(k\)-colorability threshold by counting covers, On the chromatic number of random regular graphs, Phase transitions in theq-coloring of random hypergraphs, The replica symmetric solution for orthogonally constrained Heisenberg model on Bethe lattice, On the dynamics of the glass transition on Bethe lattices, Planting Colourings Silently, Threshold saturation in spatially coupled constraint satisfaction problems, Gibbs states and the set of solutions of random constraint satisfaction problems, Spin-glass behaviour on random lattices, Calculation of the 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz, Random field Ising model in two dimensions: Bethe approximation, cluster variational method and message passing algorithms, Circular coloring of random graphs: statistical physics investigation, Interactive genetic algorithm with fitness modeling for the development of a color simulation system based on customer's preference, Pairs of SAT-assignments in random Boolean formulæ, Why almost all \(k\)-colorable graphs are easy to color, Gibbs measures and phase transitions on sparse random graphs, Almost all graphs with average degree 4 are 3-colorable, On the survey-propagation equations in random constraint satisfiability problems, A hard-sphere model on generalized Bethe lattices: dynamics, Random multi-index matching problems, Geometrical organization of solutions to random linear Boolean equations, Statistical and algebraic analysis of a family of random Boolean equations, Rigid Colorings of Hypergraphs and Contiguity, The number of matchings in random graphs, An efficient local search method for random 3-satisfiability, Compressed sensing reconstruction using expectation propagation, Spines of random constraint satisfaction problems: definition and connection with computational complexity
Cites Work
