Lower bounds on the chromatic number of random graphs

DOI10.1007/s00493-021-4236-zOpenAlexW3210957655MaRDI QIDQ2678448

Peter Ayre, Catherine Greenhill, Amin Coja-Oghlan

Publication date: 23 January 2023

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberrandom graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Related Items

Improved replica bounds for the independence ratio of random regular graphs, Rigid Colorings of Hypergraphs and Contiguity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spin glass models from the point of view of spin distributions
• Upper-bounding the \(k\)-colorability threshold by counting covers
• On the chromatic number of random regular graphs
• The asymptotic \(k\)-SAT threshold
• On the chromatic number of random graphs
• On the chromatic number of random \(d\)-regular graphs
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• Expose-and-merge exploration and the chromatic number of a random graph
• On the independence and chromatic numbers of random regular graphs
• The concentration of the chromatic number of random graphs
• The 3-XORSAT threshold.
• Information-theoretic thresholds from the cavity method
• Replica bounds by combinatorial interpolation for diluted spin systems
• 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
• Spin systems on Bethe lattices
• Maximum independent sets on random regular graphs
• Random regular graphs of high degree
• Proof of the Satisfiability Conjecture for Large k
• Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number
• Colouring Random Regular Graphs
• Information, Physics, and Computation
• On the chromatic number of a random 5-regular graph
• The Chromatic Number of Random Graphs for Most Average Degrees
• The Sherrington-Kirkpatrick Model
• The rank of sparse random matrices
• Colouring Random 4-Regular Graphs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• 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
• Satisfiability threshold for random regular \textsc{nae-sat}
• The condensation phase transition in random graph coloring