Upper-bounding the \(k\)-colorability threshold by counting covers

zbMath1298.05285arXiv1305.0177MaRDI QIDQ396853

Amin Coja-Oghlan

Publication date: 14 August 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

phase transitionsgraph coloringrandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (26)

Phase transitions in discrete structures ⋮ On the strong chromatic number of random hypergraphs ⋮ Information-theoretic thresholds from the cavity method ⋮ On Two Limit Values of the Chromatic Number of a Random Hypergraph ⋮ Estimating the \(r\)-colorability threshold for a random hypergraph ⋮ Upper-bounding the \(k\)-colorability threshold by counting covers ⋮ Inter-generational comparison of quantum annealers in solving hard scheduling problems ⋮ Lower bounds on the chromatic number of random graphs ⋮ On the chromatic number of random regular graphs ⋮ On the concentration of values of \(j\)-chromatic numbers of random hypergraphs ⋮ One-step replica symmetry breaking of random regular NAE-SAT. II ⋮ On the structure of the set of panchromatic colorings of a random hypergraph ⋮ The asymptotic \(k\)-SAT threshold ⋮ Estimating the strong \(r\)-colorability threshold in random hypergraphs ⋮ Planting Colourings Silently ⋮ On the strong chromatic number of a random 3-uniform hypergraph ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ Circular coloring of random graphs: statistical physics investigation ⋮ On the chromatic numbers of random hypergraphs ⋮ A case study in programming a quantum annealer for hard operational planning problems ⋮ On the Potts antiferromagnet on random graphs ⋮ The condensation phase transition in random graph coloring ⋮ On the Number of Solutions in Random Graphk-Colouring ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ On the Concentration of the Domination Number of the Random Graph ⋮ On the chromatic number of a random hypergraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved upper bound on the non-3-colourability threshold
• Upper-bounding the \(k\)-colorability threshold by counting covers
• On the chromatic number of random graphs
• On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
• Expose-and-merge exploration and the chromatic number of a random graph
• Almost all graphs with 2. 522\(n\) edges are not 3-colorable
• The 3-XORSAT threshold.
• Bounds for diluted mean-fields spin glass models
• Replica bounds for optimization problems and diluted spin systems
• Broken replica symmetry bounds in the mean field spin glass model
• A note on the non-colorability threshold of a random graph
• Coloring Random Graphs
• Tight Bounds on the Threshold for Permuted k-Colorability
• Information, Physics, and Computation
• On colouring random graphs
• Gibbs states and the set of solutions of random constraint satisfaction problems
• The freezing threshold for k-colourings of a random graph
• Poisson Cloning Model for Random Graphs
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• On the solution-space geometry of random constraint satisfaction problems
• The chromatic number of random graphs
• The chromatic number of random graphs
• Almost all graphs with average degree 4 are 3-colorable
• The two possible values of the chromatic number of a random graph

This page was built for publication: Upper-bounding the \(k\)-colorability threshold by counting covers