A note on highly connected K_2,ℓ-minor free graphs

2023/01/05 by Bousquet, Nicolas, Pierron, Théo, Wesolek, Alexandra
#05C75 #05C83 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2301.02133

Abstract

We show that every 3-connected K_2,ℓ-minor free graph with minimum degree at least 4 has maximum degree at most 7ℓ. As a consequence, we show that every 3-connected K_2,ℓ-minor free graph with minimum degree at least 5 and no twins of degree 5 has bounded size. Our proofs use Steiner trees and nested cuts; in particular, they do not rely on Ding's characterization of K_2,ℓ-minor free graphs.

Related

• Graphs without large K_2,n-minors
• An O(tlog t) Bound for k-Connected Subgraphs in Dense K_t-Minor-Free Graphs
• Small Complete Minors Above the Extremal Edge Density
• Dense minors of graphs with independence number two
• K₆ minors in 6-connected graphs of bounded tree-width