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
    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
    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