2022/04/21 by Chudnovsky, Maria, Scott, Alex, Seymour, Paul +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2204.10119
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 c>0 there are arbitrarily large graphs with average degree at least 8-c 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 c>0 there are arbitrarily large bipartite graphs with average degree at least 8-c 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.