## 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 K_{s, t} for a fixed s and large t. Myers proved upper bounds on D (K_{s, t}) and made a conjecture on the order of magnitude of D (K_{s, t}) for a fixed s and t → ∞. He also found exact values for D (K_{2, 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 (K_{s, t}) for a fixed s and large t.

Original language | English (US) |
---|---|

Pages (from-to) | 4435-4445 |

Number of pages | 11 |

Journal | Discrete Mathematics |

Volume | 308 |

Issue number | 19 |

DOIs | |

State | Published - Oct 6 2008 |

## Keywords

- Average degree
- Complete bipartite graphs
- Graph minors

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Fingerprint

Dive into the research topics of 'On K_{s, t}-minors in graphs with given average degree'. Together they form a unique fingerprint.