A novel giant-subgraph phase-transition in sparse random k-partite graphs

DOI10.1016/J.DAM.2005.05.011MaRDI QIDQ2581553zbMATH OpenOpenAlexFDO

Authors Ulrich Voll

Publication date 10 January 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.05.011

Mathematics Subject Classification ID

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

Recommendations

• Sudden emergence of a giant k-core in a random graph
• The property of having a \(k\)-regular subgraph has a sharp threshold
• Publication:3203051
• Critical subgraphs of a random graph
• \(k\)-regular subgraphs near the \(k\)-core threshold of a random graph

Cites work

• scientific article; zbMATH DE number 1512674 (Why is no real title available?)
• scientific article; zbMATH DE number 1380613 (Why is no real title available?)
• scientific article; zbMATH DE number 858007 (Why is no real title available?)
• A note on the non-colorability threshold of a random graph
• A randomised 3-colouring algorithm
• Almost all graphs with 2. 522\(n\) edges are not 3-colorable
• Almost all graphs with average degree 4 are 3-colorable
• On the Lambert \(w\) function
• Probabilistic methods for algorithmic discrete mathematics
• Sudden emergence of a giant k-core in a random graph
• The pure literal rule threshold and cores in random hypergraphs
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• Uniquely Colourable Graphs with Large Girth

This page was built for publication: A novel giant-subgraph phase-transition in sparse random \(k\)-partite graphs

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