On the Chromatic Number of Random Graphs with a Fixed Degree Sequence

DOI10.1017/S0963548306008388zbMath1137.05066OpenAlexW2158211033WikidataQ57401491 ScholiaQ57401491MaRDI QIDQ5443802

Cliff Smyth, Michael Krivelevich, Alan M. Frieze

Publication date: 22 February 2008

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

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

zbMATH Keywords

chromatic numberrandom graphprescribed degre sequence

Mathematics Subject Classification ID

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

Related Items

SIR epidemics on random graphs with a fixed degree sequence, Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity, Random graphs with given vertex degrees and switchings, A note on the warmth of random graphs with given expected degrees, Law of large numbers for the SIR epidemic on a random graph with given degrees

Cites Work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• On the independence and chromatic numbers of random regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• Coloring graphs with sparse neighborhoods
• Asymptotic enumeration by degree sequence of graphs of high degree
• A Random Graph Model for Power Law Graphs
• Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number
• Uniform generation of random regular graphs of moderate degree
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• The chromatic number of random graphs
• The chromatic number of random graphs