The structure of \(TK_ a\)-free graphs (Q1193564)

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.