scientific article; zbMATH DE number 15869
\(\omega\)-restricted graphscompletecomponentshomomorphism basesprime factorssimplicial decompositiontree
Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
[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.
- Simplicial tree-decompositions of infinite graphs. I
- Simplicial tree-decompositions of infinite graphs. II: The existence of prime decompositions
- scientific article; zbMATH DE number 3993631
- scientific article; zbMATH DE number 48089
- Simplicial tree-decompositions of infinite graphs. III: The uniqueness of prime decompositions
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)