![](https://d3ilqtpdwi981i.cloudfront.net/gLz5tI7uRVg6-_nl0rXgzFBTLns=/425x550/smart/https://bepress-attached-resources.s3.amazonaws.com/uploads/70/d9/7d/70d97d37-4b7d-494a-8a1a-6c3ed0f69ad1/thumbnail_BPFile%20object.jpg)
Article
On Ks,t-minors in Graphs with Given Average Degree
Publications & Research
(2008)
Abstract
Let D(H) be the minimum d such that every graph G with average degree d has an H-minor. Myers and Thomason found good bounds on D(H) for almost all graphs H and proved that for 'balanced' H random graphs provide extremal examples and determine the extremal function. Examples of 'unbalanced graphs' are complete bipartite graphs Ks,t for a fixed s and large t. Myers proved upper bounds on D(Ks,t ) and made a conjecture on the order of magnitude of D(Ks,t ) for a fixed s and t → ∞. He also found exact values for D(K2,t) for an infinite series of t. In this paper, we confirm the conjecture of Myers and find asymptotically (in s) exact bounds on D(Ks,t ) for a fixed s and large t.
Keywords
- extremal function,
- bipartite graphs,
- graphs
Disciplines
Publication Date
January 1, 2008
Citation Information
Kostochka, A.V., & Prince, N. (2008). On K_{s,t}-minors in graphs with given average degree. Discrete Mathematics, 308(19), 4435-4445.