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
    0 references

    Identifiers