Dense graphs have K3,t minors

A. V. Kostochka, N. Prince

Research output: Contribution to journalArticlepeer-review


Let K3,t* denote the graph obtained from K 3,t by adding all edges between the three vertices of degree t in it. We prove that for each t<6300 and n<t+3, each n-vertex graph G with e(G)>12(t+3)(n-2)+1 has a K3,t*-minor. The bound is sharp in the sense that for every t, there are infinitely many graphs G with e(G)=12(t+3)(|V(G)|-2)+1 that have no K3,t-minor. The result confirms a partial case of the conjecture by Woodall and Seymour that every (s+t)-chromatic graph has a Ks,t-minor.

Original languageEnglish (US)
Pages (from-to)2637-2654
Number of pages18
JournalDiscrete Mathematics
Issue number20
StatePublished - Oct 28 2010


  • Bipartite minors
  • Dense graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Dense graphs have K3,t minors'. Together they form a unique fingerprint.

Cite this