The extremal function for Petersen minors

Abstract

We prove that every graph with $n$ vertices and at least $5n-8$ 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 $5n-11$ 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.

References in corpus (4)

• Novikov's Conjecture
• Thomassen's Choosability Argument Revisited
• On triangles in K_r-minor free graphs
• K_6 minors in 6-connected graphs of bounded tree-width

Cited by in corpus (7)

• Defective colouring of graphs excluding a subgraph or minor
• Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth
• A lower bound on the average degree forcing a minor
• Extremal functions for sparse minors
• Structural properties of bipartite subgraphs
• The extremal function for bipartite linklessly embeddable graphs
• Limits of degeneracy for colouring graphs with forbidden minors