Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903853 | Journal of Combinatorial Theory, Series B | 2018 | 34 Pages |
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
Kevin Hendrey, David R. Wood,