Journal of Combinatorics

Volume 2 (2011)

Number 3

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

Pages: 463 – 479

DOI: http://dx.doi.org/10.4310/JOC.2011.v2.n3.a7

Authors

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

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

Abstract

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)