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

DOI10.4310/JOC.2011.V2.N3.A7MaRDI QIDQ446012zbMATH OpenOpenAlexFDO

Authors Roi Krakovski, Elad Aigner-Horev

Publication date 28 August 2012

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.5795

zbMATH Keywords

Jorgensen conjecture

Mathematics Subject Classification ID

Graph minors (05C83)

Abstract: We prove that every 6-connected graph of girth $geq6$ has a $K_6$-minor and thus settle the Jorgensen conjecture for graphs of girth $geq6$. Relaxing the assumption on the girth, we prove that every 6-connected $n$-vertex graph of size $geq31/5n-8$ and of girth $geq5$ contains a $K_6$-minor.

Recommendations

• On (minimal) regular graphs of girth \(6\)
• \(K_{6}\) minors in large 6-connected graphs
• \(K_{6}\) minors in 6-connected graphs of bounded tree-width
• On the domination number of graphs with minimum degree six
• K₆-minors in projective planar graphs
• Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size
• On the number of edges in a minimum \(C_6\)-saturated graph
• K₆-minors in triangulations and complete quadrangulations
• On Gallai's conjecture for graphs with maximum degree 6
• Minor-minimal 6-regular graphs in the Klein bottle

Cited in

(7)

• K₆-minors in projective planar graphs
• Simple graphs of order 12 and minimum degree 6 contain \(K_6\) minors
• Subdivisions in apex graphs
• \(K_{6}\) minors in 6-connected graphs of bounded tree-width
• Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size
• On the number of edges in a \(K_5\)-minor-free graph of given girth
• \(K_{6}\) minors in large 6-connected graphs

This page was built for publication: Extremal results regarding \(K_6\)-minors in graphs of girth at least 5

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q446012)