The extremal function for Petersen minors

Kevin Hendrey; David R. Wood

doi:10.1016/j.jctb.2018.02.001

The extremal function for Petersen minors

Kevin Hendrey, David R. Wood

School of Mathematics

Research output: Contribution to journal › Article › Research › peer-review

6 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 language	English
Pages (from-to)	220-253
Number of pages	34
Journal	Journal of Combinatorial Theory, Series B
Volume	131
DOIs	https://doi.org/10.1016/j.jctb.2018.02.001
Publication status	Published - 1 Jul 2018

Keywords

Chromatic number
Extremal function
Graph minor
Petersen graph
Vertex arboricity

Access to Document

10.1016/j.jctb.2018.02.001

Cite this

@article{62074877c97e41d5be5fa9d56f0952ae,

title = "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.",

keywords = "Chromatic number, Extremal function, Graph minor, Petersen graph, Vertex arboricity",

author = "Kevin Hendrey and Wood, {David R.}",

year = "2018",

month = jul,

day = "1",

doi = "10.1016/j.jctb.2018.02.001",

language = "English",

volume = "131",

pages = "220--253",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press",

}

TY - JOUR

T1 - The extremal function for Petersen minors

AU - Hendrey, Kevin

AU - Wood, David R.

PY - 2018/7/1

Y1 - 2018/7/1

N2 - 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.

AB - 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.

KW - Chromatic number

KW - Extremal function

KW - Graph minor

KW - Petersen graph

KW - Vertex arboricity

UR - http://www.scopus.com/inward/record.url?scp=85042500457&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2018.02.001

DO - 10.1016/j.jctb.2018.02.001

M3 - Article

AN - SCOPUS:85042500457

SN - 0095-8956

VL - 131

SP - 220

EP - 253

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

ER -

The extremal function for Petersen minors

Abstract

Keywords

Access to Document

Other files and links

Cite this