On the problem of finding small subdivision and homomorphism bases for classes of countable graphs (Q1061752)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the problem of finding small subdivision and homomorphism bases for classes of countable graphs |
scientific article |
Statements
On the problem of finding small subdivision and homomorphism bases for classes of countable graphs (English)
0 references
1985
0 references
Let \({\mathcal G}\) be a class of countable graphs given by a set \(\Gamma\) of forbidden configurations. We consider the following problem: for which \(\Gamma\) is \({\mathcal G}\) well characterized by the simplicial decompositions of its members into prime graphs, that is for which \({\mathcal G}\) is it possible to find a small subset \({\mathcal B}\) of \({\mathcal G}\) such that all graphs of \({\mathcal G}\) can be constructed from elements of \({\mathcal B}\) by successive amalgamations identifying complete subgraphs?
0 references
homomorphism base
0 references
subcontraction
0 references
countable graphs
0 references
forbidden configurations
0 references
simplicial decompositions
0 references
prime graphs
0 references