No label defined (Q3972519)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 15869
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 15869 |
Statements
25 June 1992
0 references
homomorphism bases
0 references
\(\omega\)-restricted graphs
0 references
simplicial decomposition
0 references
prime factors
0 references
components
0 references
complete
0 references
tree
0 references
0.7974424958229065
0 references
0.7967578172683716
0 references
[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.
0 references