On Ks, t-minors in graphs with given average degree

Alexandr Kostochka, Noah Prince

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)4435-4445
Number of pages11
JournalDiscrete Mathematics
Issue number19
StatePublished - Oct 6 2008


  • Average degree
  • Complete bipartite graphs
  • Graph minors

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


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

Cite this