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

DOI10.4310/JOC.2011.V2.N3.A7zbMATH Open1247.05232arXiv1012.5795OpenAlexW2043158961MaRDI QIDQ446012FDOQ446012

Authors: Roi Krakovski, Elad Aigner-Horev 

Publication date: 28 August 2012

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

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.

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

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_6\)-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

zbMATH Keywords

Jorgensen conjecture

Mathematics Subject Classification ID

Graph minors (05C83)

Cited In (7)

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

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)