On the problem of finding small subdivision and homomorphism bases for classes of countable graphs (Q1061752)

From MaRDI portal





scientific article; zbMATH DE number 3910438
Language Label Description Also known as
English
On the problem of finding small subdivision and homomorphism bases for classes of countable graphs
scientific article; zbMATH DE number 3910438

    Statements

    On the problem of finding small subdivision and homomorphism bases for classes of countable graphs (English)
    0 references
    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

    Identifiers