On the chromatic number of random regular graphs
From MaRDI portal
Publication:896008
DOI10.1016/J.JCTB.2015.09.006zbMATH Open1327.05104arXiv1308.4287OpenAlexW2101851522MaRDI QIDQ896008FDOQ896008
Authors: Amin Coja-Oghlan, Charilaos Efthymiou, Samuel Hetterich 
Publication date: 11 December 2015
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Abstract: Let G(n,d) be the random d-regular graph on n vertices. For any integer k exceeding a certain constant k_0 we identify a number d_{k-col} such that G(n,d) is k-colorable w.h.p. if d<d_{k-col} and non-k-colorable w.h.p. if d>d_{k-col}.
Full work available at URL: https://arxiv.org/abs/1308.4287
Recommendations
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Random graphs.
- Title not available (Why is that?)
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Expose-and-merge exploration and the chromatic number of a random graph
- On the independence and chromatic numbers of random regular graphs
- Coloring random graphs
- Colouring Random Regular Graphs
- On colouring random graphs
- The chromatic number of random graphs
- Information, Physics, and Computation
- Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
- The concentration of the chromatic number of random graphs
- Random regular graphs of high degree
- Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number
- Title not available (Why is that?)
- Almost all regular graphs are hamiltonian
- Random Regular Graphs: Asymptotic Distributions and Contiguity
- Colouring Random 4-Regular Graphs
- The chromatic number of random graphs
- A note on the sharp concentration of the chromatic number of random graphs
- Almost all graphs with average degree 4 are 3-colorable
- Upper-bounding the \(k\)-colorability threshold by counting covers
- On the chromatic number of random graphs
- On the chromatic number of a random 5-regular graph
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- On the chromatic number of random \(d\)-regular graphs
- Title not available (Why is that?)
- Catching the k-NAESAT threshold
Cited In (31)
- The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
- Maximum independent sets on random regular graphs
- Spin systems on Bethe lattices
- Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number
- Kolmogorov random graphs only have trivial stable colorings.
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Subgraphs of random \(k\)-edge-coloured \(k\)-regular graphs
- On the number of regular configurations
- Random Instances of Problems in NP – Algorithms and Statistical Physics
- On the chromatic number of a random 5-regular graph
- The Ising Antiferromagnet and Max Cut on Random Regular Graphs
- Random I‐colorable graphs
- On the Number of Solutions in Random Graphk-Colouring
- Regular graphs with prescribed chromatic number
- On the strong chromatic number of random graphs
- The t-improper chromatic number of random graphs
- On the chromatic number of random \(d\)-regular graphs
- On the chromatic number of the preferential attachment graph
- On the independence and chromatic numbers of random regular graphs
- Phase Transitions in Discrete Structures
- Decoding from Pooled Data: Sharp Information-Theoretic Bounds
- Random regular graphs of non-constant degree: concentration of the chromatic number
- The chromatic number of random graphs
- Title not available (Why is that?)
- The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
- Counting colorings of triangle-free graphs
- On the Potts antiferromagnet on random graphs
- One-step replica symmetry breaking of random regular NAE-SAT. II
- Lower bounds on the chromatic number of random graphs
- Planting Colourings Silently
- Metastability of the Potts ferromagnet on random regular graphs
This page was built for publication: On the chromatic number of random regular graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896008)
