The extremal function for Petersen minors

Kevin Hendrey, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)220-253
Number of pages34
JournalJournal of Combinatorial Theory, Series B
Volume131
DOIs
Publication statusPublished - 1 Jul 2018

Keywords

  • Chromatic number
  • Extremal function
  • Graph minor
  • Petersen graph
  • Vertex arboricity

Cite this