Critical subgraphs of a random graph

MaRDI QIDQ1305173zbMATH OpenFDO

Authors Michael Molloy, Bruce Reed

Publication date 16 January 2000

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/120466, http://www.emis.de/journals/EJC/Volume_6/Abstracts/v6i1r35.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

chromatic numbercritical subgraphsrandom graph

Mathematics Subject Classification ID

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

Review text

Consider \(n\) vertices and a graph process obtained by successively inserting edges at random. The threshold for a graph that is almost surely \(k\)-colorable is compared to the threshold for the appearance of a \(k\)-core.

Recommendations

• \(k\)-regular subgraphs near the \(k\)-core threshold of a random graph
• Sudden emergence of a giant k-core in a random graph
• scientific article; zbMATH DE number 1380613

Cited in

(10)

• \(k\)-regular subgraphs near the \(k\)-core threshold of a random graph
• A novel giant-subgraph phase-transition in sparse random \(k\)-partite graphs
• Strict inequalities for critical probabilities of a regular graph and a subgraph of it
• scientific article; zbMATH DE number 4091541 (Why is no real title available?)
• scientific article; zbMATH DE number 858007 (Why is no real title available?)
• scientific article; zbMATH DE number 6327467 (Why is no real title available?)
• The stripping process can be slow. II
• The critical window in random digraphs
• Color-avoiding percolation of random graphs: between the subcritical and the intermediate regime
• On the robustness of random k-cores

This page was built for publication: Critical subgraphs of a random graph

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