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.
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.
Original language | English |
---|---|
Pages (from-to) | 71-88 |
Number of pages | 18 |
Journal | Journal of the London Mathematical Society |
Volume | 91 |
Issue number | 1 |
Early online date | 5 Nov 2014 |
DOIs | |
Publication status | Published - 1 Feb 2015 |