Some remarks on universal graphs (Q5903379): Difference between revisions

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.