Logarithmically-small minors and topological minors

Research output: Contribution to journalArticlepeer-review

Colleges, School and Institutes

Abstract

For every integer t, there is a smallest real number c(t) such that any graph with average degree at least c(t) must contain a Kt-minor (proved by Mader). Improving on results of Shapira and Sudakov, we prove the conjecture of Fiorini, Joret, Theis and Wood that any graph with n vertices and average degree at least c(t)+ε must contain a Kt-minor consisting of at most C(ε,t)logn vertices.

Mader also proved that for every integer t, there is a smallest real number s(t) such that any graph with average degree larger than s(t) must contain a Kt-topological minor. We prove that, for sufficiently large t , graphs with average degree at least (1+ε)s(t) contain a Kt-topological minor consisting of at most C(ε,t)logn vertices. Finally, we show that, for sufficiently large t , graphs with average degree at least (1+ε)c(t) contain either a Kt-minor consisting of at most C(ε,t) vertices or a Kt-topological minor consisting of at most C(ε,t)logn vertices.

Details

Original languageEnglish
Pages (from-to)71-88
Number of pages18
JournalJournal of the London Mathematical Society
Volume91
Issue number1
Early online date5 Nov 2014
Publication statusPublished - 1 Feb 2015