Proper minor-closed families are small

Serguei Norine; Paul Seymour; Robin Thomas; Paul Wollan

doi:10.1016/j.jctb.2006.01.006

Proper minor-closed families are small

Serguei Norine
, Paul Seymour
, Robin Thomas
, Paul Wollan

Mathematics

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

64 Scopus citations

Abstract

We prove that for every proper minor-closed class I of graphs there exists a constant c such that for every integer n the class I includes at most n ! cⁿ graphs with vertex-set {1, 2, ..., n}. This answers a question of Welsh.

Original language	English (US)
Pages (from-to)	754-757
Number of pages	4
Journal	Journal of Combinatorial Theory. Series B
Volume	96
Issue number	5
DOIs	https://doi.org/10.1016/j.jctb.2006.01.006
State	Published - Sep 2006

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Graph
Minor
Minor-closed family

Access to Document

10.1016/j.jctb.2006.01.006

Cite this

@article{6eb5a68e1b7642d2a9aec312612d617d,

title = "Proper minor-closed families are small",

abstract = "We prove that for every proper minor-closed class I of graphs there exists a constant c such that for every integer n the class I includes at most n ! cn graphs with vertex-set \{1, 2, ..., n\}. This answers a question of Welsh.",

keywords = "Graph, Minor, Minor-closed family",

author = "Serguei Norine and Paul Seymour and Robin Thomas and Paul Wollan",

note = "Funding Information: 1 Partially supported by ONR Grant N00014-01-1-0608 and NSF Grant DMS-0070912. 2 Partially supported by NSF Grant DMS-0200595.",

year = "2006",

month = sep,

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

language = "English (US)",

volume = "96",

pages = "754--757",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "5",

}

TY - JOUR

T1 - Proper minor-closed families are small

AU - Norine, Serguei

AU - Seymour, Paul

AU - Thomas, Robin

AU - Wollan, Paul

N1 - Funding Information: 1 Partially supported by ONR Grant N00014-01-1-0608 and NSF Grant DMS-0070912. 2 Partially supported by NSF Grant DMS-0200595.

PY - 2006/9

Y1 - 2006/9

N2 - We prove that for every proper minor-closed class I of graphs there exists a constant c such that for every integer n the class I includes at most n ! cn graphs with vertex-set {1, 2, ..., n}. This answers a question of Welsh.

AB - We prove that for every proper minor-closed class I of graphs there exists a constant c such that for every integer n the class I includes at most n ! cn graphs with vertex-set {1, 2, ..., n}. This answers a question of Welsh.

KW - Graph

KW - Minor

KW - Minor-closed family

UR - https://www.scopus.com/pages/publications/33744507576

UR - https://www.scopus.com/pages/publications/33744507576#tab=citedBy

U2 - 10.1016/j.jctb.2006.01.006

DO - 10.1016/j.jctb.2006.01.006

M3 - Article

AN - SCOPUS:33744507576

SN - 0095-8956

VL - 96

SP - 754

EP - 757

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 5

ER -

Proper minor-closed families are small

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this