Bipartite graphs with no K6 minor

Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl

doi:10.1016/j.jctb.2023.08.005

Bipartite graphs with no K₆ minor

Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Mathematics

Princeton University

Research output: Contribution to journal › Article › peer-review

Abstract

A theorem of Mader shows that every graph with average degree at least eight has a K₆ 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₆ 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₆ 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₆ 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₆ minor. Indeed, it is enough that every vertex in the larger part of the bipartition has degree at least six.

Original language	American English
Pages (from-to)	68-104
Number of pages	37
Journal	Journal of Combinatorial Theory. Series B
Volume	164
DOIs	https://doi.org/10.1016/j.jctb.2023.08.005
State	Published - Jan 2024

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Bipartite
Edge-density
Minors

Access to Document

10.1016/j.jctb.2023.08.005

Cite this

@article{e2142cb2939f4a49abf647b720aa0c45,

title = "Bipartite graphs with no K6 minor",

abstract = "A theorem of Mader shows that every graph with average degree at least eight has a K6 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 K6 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 K6 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 K6 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 K6 minor. Indeed, it is enough that every vertex in the larger part of the bipartition has degree at least six.",

keywords = "Bipartite, Edge-density, Minors",

author = "Maria Chudnovsky and Alex Scott and Paul Seymour and Sophie Spirkl",

note = "Publisher Copyright: {\textcopyright} 2023 The Author(s)",

year = "2024",

month = jan,

doi = "10.1016/j.jctb.2023.08.005",

language = "American English",

volume = "164",

pages = "68--104",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Bipartite graphs with no K6 minor

AU - Chudnovsky, Maria

AU - Scott, Alex

AU - Seymour, Paul

AU - Spirkl, Sophie

PY - 2024/1

Y1 - 2024/1

N2 - A theorem of Mader shows that every graph with average degree at least eight has a K6 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 K6 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 K6 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 K6 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 K6 minor. Indeed, it is enough that every vertex in the larger part of the bipartition has degree at least six.

AB - A theorem of Mader shows that every graph with average degree at least eight has a K6 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 K6 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 K6 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 K6 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 K6 minor. Indeed, it is enough that every vertex in the larger part of the bipartition has degree at least six.

KW - Bipartite

KW - Edge-density

KW - Minors

UR - http://www.scopus.com/inward/record.url?scp=85171854444&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85171854444&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2023.08.005

DO - 10.1016/j.jctb.2023.08.005

M3 - Article

SN - 0095-8956

VL - 164

SP - 68

EP - 104

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -