On the chromatic number of random regular graphs

DOI10.1016/J.JCTB.2015.09.006MaRDI QIDQ896008zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

graph coloringphase transitionsrandom graphs

Mathematics Subject Classification ID

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

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}.

Recommendations

• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• On the chromatic number of random \(d\)-regular graphs
• Colouring Random Regular Graphs
• scientific article; zbMATH DE number 1380613
• Colouring Random 4-Regular Graphs

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1380613 (Why is no real title available?)
• scientific article; zbMATH DE number 3440485 (Why is no real title available?)
• A note on the sharp concentration of the chromatic number of random graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Almost all graphs with average degree 4 are 3-colorable
• Almost all regular graphs are hamiltonian
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Catching the \(k\)-NAESAT threshold
• Coloring random graphs
• Colouring Random 4-Regular Graphs
• Colouring Random Regular Graphs
• Expose-and-merge exploration and the chromatic number of a random graph
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Information, Physics, and Computation
• On colouring random graphs
• On the chromatic number of a random 5-regular graph
• On the chromatic number of random \(d\)-regular graphs
• On the chromatic number of random graphs
• On the independence and chromatic numbers of random regular graphs
• Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Random graphs.
• Random regular graphs of high degree
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• The chromatic number of random graphs
• The chromatic number of random graphs
• The concentration of the chromatic number of random graphs
• The condensation phase transition in random graph coloring
• Upper-bounding the \(k\)-colorability threshold by counting covers

Cited in

(32)

• On the chromatic number of a random 5-regular graph
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Maximum independent sets on random regular graphs
• Random instances of problems in NP -- algorithms and statistical physics
• Lower bounds on the chromatic number of random graphs
• scientific article; zbMATH DE number 2113521 (Why is no real title available?)
• A Ramsey property of random regular and \(k \)-out graphs
• Metastability of the Potts ferromagnet on random regular graphs
• Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number
• On the chromatic number of the preferential attachment graph
• Regular graphs with prescribed chromatic number
• Spin systems on Bethe lattices
• On the Potts antiferromagnet on random graphs
• Random I‐colorable graphs
• Random regular graphs of non-constant degree: concentration of the chromatic number
• The Ising Antiferromagnet and Max Cut on Random Regular Graphs
• Planting colourings silently
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Decoding from pooled data: sharp information-theoretic bounds
• Subgraphs of random \(k\)-edge-coloured \(k\)-regular graphs
• On the number of solutions in random graph \(k\)-colouring
• The t-improper chromatic number of random graphs
• Phase transitions in discrete structures
• Kolmogorov random graphs only have trivial stable colorings.
• Counting colorings of triangle-free graphs
• On the number of regular configurations
• On the chromatic number of random \(d\)-regular graphs
• The chromatic number of random graphs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• On the strong chromatic number of random graphs
• One-step replica symmetry breaking of random regular NAE-SAT. II
• On the independence and chromatic numbers of 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)