Article ID Journal Published Year Pages File Type
8903853 Journal of Combinatorial Theory, Series B 2018 34 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,