## Abstract

A theorem of Mader shows that every graph with average degree at least eight has a K_{6} minor, and this is false if we replace eight by any smaller constant. Replacing average degree by minimum degree seems to make little difference: we do not know whether all graphs with minimum degree at least seven have K_{6} minors, but minimum degree six is certainly not enough. For every ε>0 there are arbitrarily large graphs with average degree at least 8−ε and minimum degree at least six, with no K_{6} minor. But what if we restrict ourselves to bipartite graphs? The first statement remains true: for every ε>0 there are arbitrarily large bipartite graphs with average degree at least 8−ε and no K_{6} minor. But surprisingly, going to minimum degree now makes a significant difference. We will show that every bipartite graph with minimum degree at least six has a K_{6} minor. Indeed, it is enough that every vertex in the larger part of the bipartition has degree at least six.

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

Pages (from-to) | 68-104 |

Number of pages | 37 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 164 |

DOIs | |

State | Published - Jan 2024 |

## All Science Journal Classification (ASJC) codes

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

## Keywords

- Bipartite
- Edge-density
- Minors

## Fingerprint

Dive into the research topics of 'Bipartite graphs with no K_{6}minor'. Together they form a unique fingerprint.