The extremal function for Petersen minors
From MaRDI portal
Abstract: We prove that every graph with vertices and at least edges contains the Petersen graph as a minor, and this bound is best possible. Moreover we characterise all Petersen-minor-free graphs with at least edges. It follows that every graph containing no Petersen minor is 9-colourable and has vertex arboricity at most 5. These results are also best possible.
Recommendations
Cites work
- \(K_{6}\) minors in large 6-connected graphs
- A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
- A characterization of graphs with no octahedron minor
- A note on primitive skew curves
- A splitter for graphs with no Petersen family minor
- An extremal function for contractions of graphs
- Average degree conditions forcing a minor
- Coloring graphs with forbidden minors
- Contractions to k8
- Cycles of Given Size in a Dense Graph
- Cyclically five-connected cubic graphs
- Dense graphs have \(K_{3,t}\) minors
- Disjoint unions of complete minors
- Excluded minors in cubic graphs
- Forcing a sparse minor
- Forcing unbalanced complete bipartite minors
- Graphs with no \(\bar{P}_7\)-minor
- Graphs with the Circuit Cover Property
- Hadwiger's conjecture
- Homomorphiesätze für Graphen
- Homomorphism theorems for graphs
- scientific article; zbMATH DE number 3831963 (Why is no real title available?)
- scientific article; zbMATH DE number 3865318 (Why is no real title available?)
- scientific article; zbMATH DE number 3102312 (Why is no real title available?)
- Lower bound of the Hadwiger number of graphs by their average degree
- On \(K_{s,t}\)-minors in graphs with given average degree
- On \(K_{s,t}\)-minors in graphs with given average degree. II
- On the algebraic theory of graph colorings
- On the critical point-arboricity graphs
- On the maximum density of graphs which have no subcontraction to \(K^ r\).
- On the vertex arboricity of planar graphs of diameter two
- On the vertex-arboricity of \(K_5\)-minor-free graphs of diameter 2
- On the vertex-arboricity of planar graphs
- On the vertex-arboricity of planar graphs without 7-cycles
- On triangles in \(K_r\)-minor free graphs
- Sachs' linkless embedding conjecture
- The edge-density for \(K_{2,t}\) minors
- The extremal function for \(K_{8}^{-}\) minors
- The extremal function for \(K_{9}\) minors
- The extremal function for complete minors
- The extremal function for disconnected minors
- The extremal function for noncomplete minors
- The Point-Arboricity of Planar Graphs
- Thomassen's choosability argument revisited
- Three-edge-colouring doublecross cubic graphs
- Tutte's edge-colouring conjecture
- Vertex partitions of \(K_{4,4}\)-minor free graphs
- Über eine Eigenschaft der ebenen Komplexe
Cited in
(12)- A splitter for graphs with no Petersen family minor
- Petersen family minors
- A lower bound on the average degree forcing a minor
- The extremal function for \(K_{9}\) minors
- Graphs with no \(\bar{P}_7\)-minor
- scientific article; zbMATH DE number 3887729 (Why is no real title available?)
- Extremal functions for sparse minors
- Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth
- Recent progress towards Hadwiger's conjecture
- On the choosability of \(H\)-minor-free graphs
- Limits of degeneracy for colouring graphs with forbidden minors
- Tight minimum degree conditions for apex-outerplanar minors and subdivisions in graphs and digraphs
This page was built for publication: The extremal function for Petersen minors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1748273)
