Journal of Combinatorics

Volume 2 (2011)

Number 3

Extremal results regarding $K_6$-minors in graphs of girth at least $5$

Pages: 463 – 479



Elad Aigner-Horev (Department of Mathematics, University of Hamburg, Germany)

Roi Krakovski (Department of Mathematics, Simon Fraser University, Burnaby, British Columbia, Canada)


We prove that every $6$-connected graph of girth $\geq6$ has a$K_6$-minor and thus settle Jorgensen’s conjecture for graphs of girth~$\geq6$.Relaxing the assumption on the girth, we prove that every $6$-connected$n$-vertex graph of size $\geq3\frac{1}{5}n-8$ and of girth $\geq5$contains a $K_6$-minor.

Full Text (PDF format)