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

DOI10.1016/j.dam.2005.05.011zbMath1078.05078OpenAlexW2041542940MaRDI QIDQ2581553

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A randomised 3-colouring algorithm
• Probabilistic methods for algorithmic discrete mathematics
• Almost all graphs with 2. 522\(n\) edges are not 3-colorable
• On the Lambert \(w\) function
• Sudden emergence of a giant \(k\)-core in a random graph
• A note on the non-colorability threshold of a random graph
• Uniquely Colourable Graphs with Large Girth
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• 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