Circular coloring of random graphs: statistical physics investigation

DOI10.1088/1742-5468/2016/08/083303zbMath1456.05152arXiv1605.06945OpenAlexW2396498273MaRDI QIDQ3302790

Lenka Zdeborová, Nils-Eric Guenther, Christian Schmidt

Publication date: 11 August 2020

Published in: Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1605.06945

Mathematics Subject Classification ID

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

Related Items (2)

Phase transitions in theq-coloring of random hypergraphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Upper-bounding the \(k\)-colorability threshold by counting covers
• The asymptotic \(k\)-SAT threshold
• Random cubic graphs are not homomorphic to the cycle of size 7
• Regular graphs with no homomorphisms onto cycles
• The cavity method at zero temperature
• Coloring Random Graphs
• Tight Bounds on the Threshold for Permuted k-Colorability
• Information, Physics, and Computation
• On the out-of-equilibrium relaxation of the Sherrington-Kirkpatrick model
• Survey propagation: An algorithm for satisfiability
• Gibbs states and the set of solutions of random constraint satisfaction problems
• A Combinatorial Classic — Sparse Graphs with High Chromatic Number
• The condensation transition in random hypergraph 2-coloring
• Colorings and homomorphisms of degenerate and bounded degree graphs
• The condensation phase transition in random graph coloring

This page was built for publication: Circular coloring of random graphs: statistical physics investigation