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

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