The order of the largest complete minor in a random graph

DOI10.1016/j.endm.2007.07.023zbMath1341.05228arXiv0705.0325OpenAlexW2005828013MaRDI QIDQ5900071

Daniela Kühn, Nikolaos Fountoulakis, Deryk Osthus

Publication date: 5 June 2008

Published in: Electronic Notes in Discrete Mathematics, Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0705.0325

zbMATH Keywords

random graphsextremal problemgraph minors

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Graph minors (05C83)

Related Items (8)

Waiter-Client and Client-Waiter planarity, colorability and minor games ⋮ Large complete minors in random subgraphs ⋮ Complete Minors in Graphs Without Sparse Cuts ⋮ Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets ⋮ Finding and Using Expanders in Locally Sparse Graphs ⋮ Characterisations and examples of graph classes with bounded expansion ⋮ Minors in random regular graphs ⋮ Expansion in supercritical random subgraphs of the hypercube and its consequences

Cites Work

• Topological cliques of random graphs
• Lower bound of the Hadwiger number of graphs by their average degree
• Minors in expanding graphs
• Hadwiger's conjecture is true for almost every graph
• The longest path in a random graph
• On the conjecture of Hajos
• The extremal function for complete minors
• An extremal function for contractions of graphs
• The Structure of a Random Graph at the Point of the Phase Transition
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The order of the largest complete minor in a random graph