THE STRUCTURE OF TKA-FREE GRAPHS

A well-known theorem of Halin implies that the graphs not containing a TKa, where a is any regular uncountable cardinal, can be decomposed into induced subgraphs of order < a which are arranged in a tree-like fashion. We formalize this observation by introducing the new concept of a generalized tree-decomposition, which is shown to extend in a natural way the familiar tree-decompositions of finite graphs. We then proved that the TKa-free graphs can be characterized purely in terms of these decompositions: a graph is TKa-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. © 1992.