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

DOI10.1016/J.DAM.2005.05.011zbMATH Open1078.05078OpenAlexW2041542940MaRDI QIDQ2581553FDOQ2581553

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

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

Mathematics Subject Classification ID

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

Cites Work

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

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)