On the existence of countable universal graphs

DOI10.1002/(SICI)1097-0118(199705)25:1%3C53::AID-JGT3%3E3.0.CO;2-HMaRDI QIDQ4337505zbMATH OpenOpenAlexFDO

Authors Péter Komjáth, Zoltán Füredi

Publication date 19 May 1997

Full work available at URL https://doi.org/10.1002/(sici)1097-0118(199705)25:1%3C53::aid-jgt3%3E3.0.co;2-h

zbMATH Keywords

2-connectedcountable universal graphsforbidden subgraphnearly disjoint hypergraphuniversal element

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Hypergraphs (05C65)

Review text

Given a graph \(G\) let \(\text{Forb}(G)\) be the class of all countable graphs containing no subgraph isomorphic to \(G\) (``subgraph does not necessarily mean induced subgraph). A graph \(U\in\text{Forb}(G)\) is said to be a universal element, if any other graph from \(\text{Forb}(G)\) is isomorphic to a subgraph of \(U\). The following theorem is proved: Let \(G\) be a finite graph and let \(B\) be a 2-connected, noncomplete block in \(G\) which is not isomorphic to a subgraph of another 2-connected block in \(G\). Then \(\text{Forb}(G)\) has no universal element. Further problems and conjectures are presented.

Recommendations

• On universal graphs with forbidden topological subgraphs
• Universal graphs with a forbidden subtree
• Some remarks on universal graphs
• Universal graphs with a forbidden subgraph: block path solidity
• There is no universal countable pentagon‐free graph

Cited in

(30)

• Representation of ideals of relational structures
• Universal elements and the complexity of certain classes of infinite graphs
• Universal graphs with forbidden subgraphs and algebraic closure
• Nonexistence of universal graphs without some trees
• Universal graphs with a forbidden subgraph: block path solidity
• Hadwiger's conjecture for uncountable graphs
• There is no universal countable random-free graph
• Forbidden substructures and combinatorial dichotomies: WQO and universality
• All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)
• On universal positive graphs
• Forbidden subgraphs and forbidden substructures
• The countable character of uncountable graphs
• Existence and nonexistence of universal graphs
• Universal graphs for two graph properties.
• The research of the existence of universal hypergraphs
• scientific article; zbMATH DE number 3954975 (Why is no real title available?)
• There is no universal countable pentagon‐free graph
• scientific article; zbMATH DE number 1072415 (Why is no real title available?)
• scientific article; zbMATH DE number 1117459 (Why is no real title available?)
• Some remarks on universal graphs
• Some remarks on universal graphs
• Countable \(\alpha\)-extendable graphs
• A note on classes of subgraphs of locally finite graphs
• Universal graphs for the topological minor relation
• Bowtie‐free graphs and generic automorphisms
• Universal graphs with forbidden wheel minors
• On graph classes with minor-universal elements
• Faithful universal graphs for minor-closed classes
• Universal graphs with a forbidden subtree
• Universality and asymptotics of graph counting problems in non-orientable surfaces

This page was built for publication: On the existence of countable universal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4337505)