Some remarks on universal graphs (Q5903379)

From MaRDI portal
scientific article; zbMATH DE number 4004224
Language Label Description Also known as
English
Some remarks on universal graphs
scientific article; zbMATH DE number 4004224

    Statements

    Some remarks on universal graphs (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    1985
    0 references
    Let \(\Gamma\) be a class of countable graphs, and let \({\mathcal G}(\Gamma)\) denote the class of all countable graphs that do not contain any subgraph isomorphic to a member of \(\Gamma\). Furthermore, let \(T\Gamma\) and \(H\Gamma\) denote the class of all subdivisions of graphs in \(\Gamma\) and the class of all graphs contracting to a member of \(\Gamma\), respectively. As the main result of this paper it is decided which of the classes \({\mathcal G}(TK^ n)\) and \({\mathcal G}(HK^ n)\), \(n\leq \aleph_ 0\), contain a universal element. In fact, for \({\mathcal G}(TK^ 4)={\mathcal G}(HK^ 4)\) a strongly universal graph is constructed, whereas for \(5\leq n\leq \aleph_ 0\) the classes \({\mathcal G}(TK^ n)\) and \({\mathcal G}(HK^ n)\) have no universal elements.
    0 references
    0 references
    countable graphs
    0 references
    strongly universal graph
    0 references
    0 references