The freezing threshold for k-colourings of a random graph

DOI10.1145/2213977.2214060zbMath1286.05049OpenAlexW1991809010MaRDI QIDQ5415525

No author found.

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2213977.2214060

zbMATH Keywords

clusteringcolouringrandom graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Related Items (26)

Phase transitions in discrete structures ⋮ How does the core sit inside the mantle? ⋮ Information-theoretic thresholds from the cavity method ⋮ On the number of solutions in random hypergraph 2-colouring ⋮ The asymptotics of the clustering transition for random constraint satisfaction problems ⋮ Complexity of Coloring Random Graphs ⋮ Upper-bounding the \(k\)-colorability threshold by counting covers ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ The asymptotic \(k\)-SAT threshold ⋮ Phase transitions in theq-coloring of random hypergraphs ⋮ Planting Colourings Silently ⋮ On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ Charting the replica symmetric phase ⋮ Constraining the clustering transition for colorings of sparse random graphs ⋮ Unnamed Item ⋮ Local convergence of random graph colorings ⋮ On the Potts antiferromagnet on random graphs ⋮ The condensation phase transition in random graph coloring ⋮ On the Number of Solutions in Random Graphk-Colouring ⋮ Core forging and local limit theorems for the \(k\)-core of random graphs ⋮ Rigid Colorings of Hypergraphs and Contiguity ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Biased landscapes for random constraint satisfaction problems ⋮ Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion ⋮ Minimal contagious sets in random regular graphs

This page was built for publication: The freezing threshold for k-colourings of a random graph