Graph minors. VIII. A kuratowski theorem for general surfaces

Neil Robertson; P. D. Seymour

doi:10.1016/0095-8956(90)90121-F

Graph minors. VIII. A kuratowski theorem for general surfaces

Neil Robertson, P. D. Seymour

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

92 Scopus citations

Abstract

We prove that for any infinite set of graphs of bounded genus, some member of the set is isomorphic to a minor of another. As a consequence, for any surface Σ there is a finite list of graphs, such that a general graph may be drawn in Σ if an only if it topologically contains none of the graphs in the list.

Original language	English (US)
Pages (from-to)	255-288
Number of pages	34
Journal	Journal of Combinatorial Theory, Series B
Volume	48
Issue number	2
DOIs	https://doi.org/10.1016/0095-8956(90)90121-F
State	Published - Apr 1990
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/0095-8956(90)90121-F

Cite this

@article{4d51e27972a5483091724a1f36a854a9,

title = "Graph minors. VIII. A kuratowski theorem for general surfaces",

abstract = "We prove that for any infinite set of graphs of bounded genus, some member of the set is isomorphic to a minor of another. As a consequence, for any surface Σ there is a finite list of graphs, such that a general graph may be drawn in Σ if an only if it topologically contains none of the graphs in the list.",

author = "Neil Robertson and Seymour, {P. D.}",

note = "Funding Information: supported by NSF grant MCS 8103440. 255",

year = "1990",

month = apr,

doi = "10.1016/0095-8956(90)90121-F",

language = "English (US)",

volume = "48",

pages = "255--288",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Graph minors. VIII. A kuratowski theorem for general surfaces

AU - Robertson, Neil

AU - Seymour, P. D.

N1 - Funding Information: supported by NSF grant MCS 8103440. 255

PY - 1990/4

Y1 - 1990/4

N2 - We prove that for any infinite set of graphs of bounded genus, some member of the set is isomorphic to a minor of another. As a consequence, for any surface Σ there is a finite list of graphs, such that a general graph may be drawn in Σ if an only if it topologically contains none of the graphs in the list.

AB - We prove that for any infinite set of graphs of bounded genus, some member of the set is isomorphic to a minor of another. As a consequence, for any surface Σ there is a finite list of graphs, such that a general graph may be drawn in Σ if an only if it topologically contains none of the graphs in the list.

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

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

U2 - 10.1016/0095-8956(90)90121-F

DO - 10.1016/0095-8956(90)90121-F

M3 - Article

AN - SCOPUS:38249020670

SN - 0095-8956

VL - 48

SP - 255

EP - 288

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 2

ER -

Graph minors. VIII. A kuratowski theorem for general surfaces

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this