The structure of \(TK_ a\)-free graphs (Q1193564)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The structure of \(TK_ a\)-free graphs |
scientific article |
Statements
The structure of \(TK_ a\)-free graphs (English)
0 references
27 September 1992
0 references
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.
0 references
\(TK_ a\)-free graphs
0 references
tree-decomposition
0 references
characterization
0 references
structure
0 references
normal spanning trees
0 references