How Sharp is the Concentration of the Chromatic Number?

DOI10.1017/S0963548303006060MaRDI QIDQ4813870zbMATH OpenOpenAlexFDO

Authors Béla Bollobás

Publication date 7 September 2004

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548303006060

zbMATH Keywords

random graphchromatic numberconcentration

Mathematics Subject Classification ID

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

Recommendations

• Non-concentration of the chromatic number of a random graph
• The concentration of the chromatic number of random graphs
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• A note on the chromatic number of a dense random graph
• Random regular graphs of non-constant degree: concentration of the chromatic number

Cited in

(9)

• How does the chromatic number of a random graph vary?
• One-point concentration of the clique and chromatic numbers of the random Cayley graph on \(\mathbb{F}_2^n\)
• Complexity of coloring random graphs: an experimental study of the hardest region
• Two values of the chromatic number of a sparse random graph
• A note on the chromatic number of a dense random graph
• On the concentration of the chromatic number of random graphs
• On the chromatic number in the stochastic block model
• Sharp concentration of the equitable chromatic number of dense random graphs
• Non-concentration of the chromatic number of a random graph

This page was built for publication: How Sharp is the Concentration of the Chromatic Number?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4813870)