The structure of \(TK_ a\)-free graphs
type: Item
instance of: scholarly article
title: The structure of \(TK_ a\)-free graphs
zbMATH Open document ID: 0764.05078
DOI: 10.1016/0095-8956(92)90054-2
published in: Journal of Combinatorial Theory. Series B
publication date: 1992-09-27T00:00:00Z
review text: A well-known theorem of Halin implies that the graphs not containing a \(TK_ a\), where \(a\) is any regular uncountable cardinal, can be decomposed into induced subgraphs of order \(<a\) which are arranged in a tree-like fashion. This observation is formalized by the new concept of a generalized tree-decomposition, which is shown to extend in a natural way the familiar tree-decomposition of finite graphs. If is proved that the \(TK_ a\)-free graphs can be characterized purely in terms of these decompositions: a graph is \(TK_ a\)-free if and only if it admits a generalized tree-decomposition into subgraphs of order \(<a\) such that every branch of the corresponding decomposition tree has length \(<a\). This result was obtained concurrently and independently by N. Robertson, P. D. Seymour and R. Thomas, who also extended it to singular \(a\) and to \(a=\aleph_ 0\). This latter characterization has in turn been refined by the author, in a recent note which describes the structure of the \(TK_{aleph_ 0}\)-free graphs in terms of their normal spanning trees.
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 64852
zbMATH Keywords: \(TK_ a\)-free graphs
zbMATH Keywords: tree-decomposition
zbMATH Keywords: characterization
zbMATH Keywords: structure
zbMATH Keywords: normal spanning trees
author: Reinhard Diestel
MaRDI profile type: Publication
full work available at URL: 0095-8956(92)90054-2
OpenAlex ID: W204002426
cites work: Simplicial tree-decompositions of infinite graphs. I
cites work: Q3999150
cites work: Ein Zerlegungssatz für unendliche Graphen und seine Anwendung auf Homomorphiebasen
cites work: Unterteilungen vollständiger Graphen in Graphen mit unendlicher chromatischer Zahl
cites work: Q4117857
cites work: Zusammenzüge und Unterteilungen von Graphen
cites work: Graph minors. XVIII: Tree-decompositions and well-quasi-ordering
description: scientific article; zbMATH DE number 64852