Authors
Citation
A. Thomason, The extremal function for complete minors, J COMB TH B, 81(2), 2001, pp. 318-338
Citations number
26
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956
→ ACNP
Volume
81
Issue
2
Year of publication
2001
Pages
318 - 338
Database
ISI
SICI code
0095-8956(200103)81:2<318:TEFFCM>2.0.ZU;2-J
Abstract
Let c(t) be the minimum number c such that every graph G with c(G)greater t
han or equal toc \G \ contracts to a complete graph K-p. We show that
c(t) = (alpha + o(1))t log t
where x=0.319... is an explicit constant. Random graphs are extremal graphs
. (C) 2001 Academic Press.