scientific article; zbMATH DE number 15869

From MaRDI portal
Publication:3972519





[For the entire collection see Zbl 0709.00011.] The author calls a graph \(G\) \(\omega\)-restricted if \(G\) contains no complete infinite graph \(K_ \omega\) and any two non-adjacent vertices can be separated by a finite set of vertices. For example, all edge- maximal graphs with respect to a given class of forbidden finite minors are \(\omega\)-restricted. The central concept in the paper is that of a ``simplicial decomposition as introduced by K. Wagner and studied by the author in a series of papers. In an earlier paper the author showed that a graph \(G\) not containing \(K_ \omega\) has a simplicial decomposition into prime factors. For \(\omega\)-restricted graphs it is shown that the prime factors are countable and can be characterized without using the axiom of choice. The general case \(G\not\supseteq K_ \omega\) is reduced to \(\omega\)-restricted graphs by the notion of a ``pseudo-simplicial decomposition (see Theorem \(2'\)). It is further shown that an \(\omega\)-restricted connected graph \(G\) either contains a complete subgraph \(S\) such that \(G-S\) has infinitely many components or else contains a locally finite spanning tree. In a prime \(\omega\)- restricted graph each vertex of infinite degree can be joined by an infinity of openly disjoint paths to some ray \(R\), and the set of vertices, which in this way are associated to \(R\), is complete. In another section \(\omega\)-restricted graphs not containing infinitely many disjoint rays are investigated in more detail. In the final section it is shown that prime \(\omega\)-restricted graphs allow a ``proper-tree-like decomposition with a locally finite decomposition tree.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3972519)