Excluding infinite trees

P. D. Seymour; Robin Thomas

doi:10.1090/S0002-9947-1993-1079058-6

Excluding infinite trees

P. D. Seymour, Robin Thomas

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

3 Scopus citations

Abstract

For each infinite cardinal k we give several necessary and sufficient conditions for a graph not to contain a minor isomorphic to the infinite k-branching tree in terms of a certain kind of a “tree-decomposition,” in terms of a “path-decomposition,” and alsoin terms of a “cops-and-robber game.” We also give necessary and sufficient conditions for a graph not to contain a subgraph isomorphic to a subdivision of the same tree.

Original language	English (US)
Pages (from-to)	597-630
Number of pages	34
Journal	Transactions of the American Mathematical Society
Volume	335
Issue number	2
DOIs	https://doi.org/10.1090/S0002-9947-1993-1079058-6
State	Published - 1993
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics
Applied Mathematics

Access to Document

10.1090/S0002-9947-1993-1079058-6

Cite this

@article{b5e67fcd3e92476f8f6c28d8df052850,

title = "Excluding infinite trees",

abstract = "For each infinite cardinal k we give several necessary and sufficient conditions for a graph not to contain a minor isomorphic to the infinite k-branching tree in terms of a certain kind of a “tree-decomposition,” in terms of a “path-decomposition,” and alsoin terms of a “cops-and-robber game.” We also give necessary and sufficient conditions for a graph not to contain a subgraph isomorphic to a subdivision of the same tree.",

author = "Seymour, {P. D.} and Robin Thomas",

year = "1993",

doi = "10.1090/S0002-9947-1993-1079058-6",

language = "English (US)",

volume = "335",

pages = "597--630",

journal = "Transactions of the American Mathematical Society",

issn = "0002-9947",

publisher = "American Mathematical Society",

number = "2",

}

TY - JOUR

T1 - Excluding infinite trees

AU - Seymour, P. D.

AU - Thomas, Robin

PY - 1993

Y1 - 1993

N2 - For each infinite cardinal k we give several necessary and sufficient conditions for a graph not to contain a minor isomorphic to the infinite k-branching tree in terms of a certain kind of a “tree-decomposition,” in terms of a “path-decomposition,” and alsoin terms of a “cops-and-robber game.” We also give necessary and sufficient conditions for a graph not to contain a subgraph isomorphic to a subdivision of the same tree.

AB - For each infinite cardinal k we give several necessary and sufficient conditions for a graph not to contain a minor isomorphic to the infinite k-branching tree in terms of a certain kind of a “tree-decomposition,” in terms of a “path-decomposition,” and alsoin terms of a “cops-and-robber game.” We also give necessary and sufficient conditions for a graph not to contain a subgraph isomorphic to a subdivision of the same tree.

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

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

U2 - 10.1090/S0002-9947-1993-1079058-6

DO - 10.1090/S0002-9947-1993-1079058-6

M3 - Article

AN - SCOPUS:0042239923

SN - 0002-9947

VL - 335

SP - 597

EP - 630

JO - Transactions of the American Mathematical Society

JF - Transactions of the American Mathematical Society

IS - 2

ER -

Excluding infinite trees

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this