The extremal function for K₈^- minors
A result of Mader from 1968, which was instrumental for the proof of the special case of Hadwiger's conjecture by Robertson, Seymour and Thomas for graphs without \(K_6\) minor, states that for \(p\leq 7\) every graph \(G\) with sufficiently many edges has a \(K_p\) minor. In the present paper the author proves a conjecture of Jakobsen from 1983 which in some sense generalizes Mader's result and might be useful to achieve progress on Hadwiger's conjecture. Specifically, he proves that every graph of order \(n\geq 8\) with at least \((11n-35)/2\) edges either has a \(K_8^-\) minor (i.e. \(K_8\) minus one edge) or is obtained from disjoint copies of \(K_{1,2,2,2,2}\) and/or \(K_7\) by identifying cliques of size five.
- 2-linked graphs
- A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
- Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor
- Contractions to k8
- Disjoint paths in graphs
- Eine Verallgemeinerung des n-fachen Zusammenhangs für Graphen
- Graph minors and linkages
- Hadwiger's conjecture for \(K_ 6\)-free graphs
- Homomorphiesätze für Graphen
- scientific article; zbMATH DE number 3102312 (Why is no real title available?)
- On a certain homomorphism properties of graphs II.
- On Certain Homomorphism Properties of Graphs I.
- The extremal function for Petersen minors
- Coloring graphs with forbidden minors
- The extremal function for \(K_{9}\) minors
- scientific article; zbMATH DE number 475585 (Why is no real title available?)
- The extremal function for \(K_9^=\) minors
- scientific article; zbMATH DE number 2188389 (Why is no real title available?)
- The spectral radius of minor-free graphs
- Maximum spread of \(K_r - E(\cup_{i = 1}^\ell P_{k_i})\)-minor-free graphs
- On embeddability and stresses of graphs
This page was built for publication: The extremal function for \(K_{8}^{-}\) minors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2573648)
