Lower bounds on the chromatic number of random graphs
From MaRDI portal
Publication:2678448
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
Related Items (2)
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
This page was built for publication: Lower bounds on the chromatic number of random graphs
