## Abstract

Let K_{3,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 K_{3,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 K_{s,t}-minor.

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

Pages (from-to) | 2637-2654 |

Number of pages | 18 |

Journal | Discrete Mathematics |

Volume | 310 |

Issue number | 20 |

DOIs | |

State | Published - Oct 28 2010 |

## Keywords

- Bipartite minors
- Dense graphs

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Fingerprint

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