Excluding infinite trees

P. D. Seymour, Robin Thomas

Research output: Contribution to journalArticle

1 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 languageEnglish (US)
Pages (from-to)597-630
Number of pages34
JournalTransactions of the American Mathematical Society
Volume335
Issue number2
DOIs
StatePublished - Jan 1 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Excluding infinite trees'. Together they form a unique fingerprint.

  • Cite this