Bipartite graphs with no K6 minor

Journal article

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

Authors: Chudnovsky, M; Scott, A; Seymour, P; Spirkl, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Journal of Combinatorial Theory: Series B
• Volume: 164
• Pages: 68-104
• Publication date: 2023-09-20
• Acceptance date: 2023-08-18
• DOI: 10.1016/j.jctb.2023.08.005
• ISSN: 0095-8956
• Language: English
• Keywords: minors; bipartite; edge-density