The edge-density for K2,t minors

Research output: Contribution to journalArticlepeer-review

29 Scopus citations

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 K2,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 languageEnglish (US)
Pages (from-to)18-46
Number of pages29
JournalJournal of Combinatorial Theory. Series B
Volume101
Issue number1
DOIs
StatePublished - Jan 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 K2,t minors'. Together they form a unique fingerprint.

Cite this