Excluding infinite minors

Neil Robertson; Paul Seymour; Robin Thomas

doi:10.1016/0012-365X(91)90343-Z

Excluding infinite minors

Neil Robertson, Paul Seymour, Robin Thomas

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

14 Scopus citations

Abstract

Let κ be an infinite cardinal, and let H be either a complete graph with κ vertices, or a tree in which every vertex has valency κ. What can we say about graphs G which (i) have no minor isomorphic to H, or (ii) contain no subgraph which is a subdivision of H? These four questions are answered for each infinite cardinal κ. In each case we find that there corresponds a necessary and sufficient structural condition (or, in some cases, several equivalent conditions) for G not to contain H in the appropriate way. We survey these results and a number of related theorems.

Original language	English (US)
Pages (from-to)	303-319
Number of pages	17
Journal	Discrete Mathematics
Volume	95
Issue number	1-3
DOIs	https://doi.org/10.1016/0012-365X(91)90343-Z
State	Published - Dec 3 1991
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(91)90343-Z

Cite this

@article{7bc9819d34964e9c83fcbe6f4f02b325,

title = "Excluding infinite minors",

abstract = "Let κ be an infinite cardinal, and let H be either a complete graph with κ vertices, or a tree in which every vertex has valency κ. What can we say about graphs G which (i) have no minor isomorphic to H, or (ii) contain no subgraph which is a subdivision of H? These four questions are answered for each infinite cardinal κ. In each case we find that there corresponds a necessary and sufficient structural condition (or, in some cases, several equivalent conditions) for G not to contain H in the appropriate way. We survey these results and a number of related theorems.",

author = "Neil Robertson and Paul Seymour and Robin Thomas",

year = "1991",

month = dec,

day = "3",

doi = "10.1016/0012-365X(91)90343-Z",

language = "English (US)",

volume = "95",

pages = "303--319",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Excluding infinite minors

AU - Robertson, Neil

AU - Seymour, Paul

AU - Thomas, Robin

PY - 1991/12/3

Y1 - 1991/12/3

N2 - Let κ be an infinite cardinal, and let H be either a complete graph with κ vertices, or a tree in which every vertex has valency κ. What can we say about graphs G which (i) have no minor isomorphic to H, or (ii) contain no subgraph which is a subdivision of H? These four questions are answered for each infinite cardinal κ. In each case we find that there corresponds a necessary and sufficient structural condition (or, in some cases, several equivalent conditions) for G not to contain H in the appropriate way. We survey these results and a number of related theorems.

AB - Let κ be an infinite cardinal, and let H be either a complete graph with κ vertices, or a tree in which every vertex has valency κ. What can we say about graphs G which (i) have no minor isomorphic to H, or (ii) contain no subgraph which is a subdivision of H? These four questions are answered for each infinite cardinal κ. In each case we find that there corresponds a necessary and sufficient structural condition (or, in some cases, several equivalent conditions) for G not to contain H in the appropriate way. We survey these results and a number of related theorems.

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

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

U2 - 10.1016/0012-365X(91)90343-Z

DO - 10.1016/0012-365X(91)90343-Z

M3 - Article

AN - SCOPUS:38149144767

SN - 0012-365X

VL - 95

SP - 303

EP - 319

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Excluding infinite minors

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this