Extremal results regarding K₆-minors in graphs of girth at least 5

2010/12/28 by Aigner-Horev, Elad, Krakovski, Roi
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1012.5795

Abstract

We prove that every 6-connected graph of girth ≥ 6 has a K₆-minor and thus settle the Jorgensen conjecture for graphs of girth ≥ 6. Relaxing the assumption on the girth, we prove that every 6-connected n-vertex graph of size ≥ 3 1/5 n-8 and of girth ≥ 5 contains a K₆-minor.

Related

• K₆ minors in 6-connected graphs of bounded tree-width
• K₆ minors in large 6-connected graphs
• Graphs without large K_2,n-minors
• Extremal K₄-minor-free graphs without short cycles
• Minors in graphs of large θ_r-girth