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

DOI10.1017/S0963548306008388MaRDI QIDQ5443802zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Michael Krivelevich, Cliff Smyth, Alan 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 numberprescribed degre sequencerandom graph

Mathematics Subject Classification ID

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

Recommendations

• Random regular graphs of non-constant degree: concentration of the chromatic number
• On the chromatic number of random graphs
• The chromatic number of random graphs for most average degrees
• A note on the chromatic number of a dense random graph
• On the chromatic number of random \(d\)-regular graphs

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A Random Graph Model for Power Law Graphs
• Asymptotic enumeration by degree sequence of graphs of high degree
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Coloring graphs with sparse neighborhoods
• On the independence and chromatic numbers of random regular graphs
• Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number
• The asymptotic number of labeled graphs with given degree sequences
• The chromatic number of random graphs
• The chromatic number of random graphs
• 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
• Uniform generation of random regular graphs of moderate degree

Cited in

(13)

• On the chromatic number of random \(d\)-regular graphs
• Random regular graphs of non-constant degree: concentration of the chromatic number
• Degree sequences and chromatic numbers of graphs
• A note on the warmth of random graphs with given expected degrees
• Extremal values of the chromatic number for a given degree sequence
• Lower bounds on the chromatic number of random graphs
• Hadwiger number and chromatic number for near regular degree sequences
• SIR epidemics on random graphs with a fixed degree sequence
• On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs
• Random graphs with given vertex degrees and switchings
• Law of large numbers for the SIR epidemic on a random graph with given degrees
• The two possible values of the chromatic number of a random graph
• Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity

This page was built for publication: On the Chromatic Number of Random Graphs with a Fixed Degree Sequence

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