A note on the chromatic number of a dense random graph

DOI10.1016/J.DISC.2008.09.019MaRDI QIDQ1025972zbMATH OpenOpenAlexFDO

Authors Angelika Steger, Konstantinos Panagiotou

Publication date 23 June 2009

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2008.09.019

zbMATH Keywords

chromatic numberrandom graphs

Mathematics Subject Classification ID

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

Recommendations

• The chromatic number of random graphs
• On the chromatic number of random graphs
• On the Chromatic Number of Random Graphs
• The chromatic number of dense random graphs
• On the chromatic number of random graphs

Cites work

• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Cliques in random graphs
• Expose-and-merge exploration and the chromatic number of a random graph
• How Sharp is the Concentration of the Chromatic Number?
• On colouring random graphs
• On the Chromatic Number of Random Graphs
• Paths in graphs
• 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 two possible values of the chromatic number of a random graph

Cited in

(19)

• How does the chromatic number of a random graph vary?
• Almost all graphs with high girth and suitable density have high chromatic number
• The chromatic number of dense random graphs
• A note on the sharp concentration of the chromatic number of random graphs
• Tight asymptotics of clique‐chromatic numbers of dense random graphs
• How Sharp is the Concentration of the Chromatic Number?
• Complexity of coloring random graphs: an experimental study of the hardest region
• The chromatic number of random graphs
• On two limit values of the chromatic number of a random hypergraph
• The Choice Number of Dense Random Graphs
• For most graphs H, most H-free graphs have a linear homogeneous set
• Clique coloring of dense random graphs
• On the Chromatic Number of Random Graphs with a Fixed Degree Sequence
• Cliques and chromatic number in multiregime random graphs
• On the chromatic number in the stochastic block model
• Sharp concentration of the equitable chromatic number of dense random graphs
• Chromatic thresholds in dense random graphs
• Non-concentration of the chromatic number of a random graph
• The average size of an independent set in graphs with a given chromatic number

This page was built for publication: A note on the chromatic number of a dense random graph

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