### Abstract

Let H be a graph. If G is an n-vertex simple graph that does not contain H as a minor, what is the maximum number of edges that G can have? This is at most linear in n, but the exact expression is known only for very few graphs H. For instance, when H is a complete graph Kt, the "natural" conjecture, (t-2)n- 1/2(t-1)-(t-2), is true only for t-7 and wildly false for large t, and this has rather dampened research in the area. Here we study the maximum number of edges when H is the complete bipartite graph K_{2,t}. We show that in this case, the analogous "natural" conjecture, 1/2(t+1)(n-1), is (for all t-2) the truth for infinitely many n.

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

Pages (from-to) | 18-46 |

Number of pages | 29 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 101 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 2011 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

### Keywords

- Extremal
- Graph
- Minors

## Fingerprint Dive into the research topics of 'The edge-density for K<sub>2,t</sub> minors'. Together they form a unique fingerprint.

## Cite this

Chudnovsky, M., Reed, B., & Seymour, P. (2011). The edge-density for K

_{2,t}minors.*Journal of Combinatorial Theory. Series B*,*101*(1), 18-46. https://doi.org/10.1016/j.jctb.2010.09.001