Universal elements and the complexity of certain classes of infinite graphs

DOI10.1016/0012-365X(91)90340-8MaRDI QIDQ1191925zbMATH OpenFDO

Authors János Pach, Péter Komjáth

Publication date 27 September 1992

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

induced subgraphhypergraphsrandom graphsisometric embeddingsuniversal element

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Hypergraphs (05C65) Graph theory (05C99)

Recommendations

• The complexity of a class of infinite graphs
• On universal graphs for hom-properties
• On the existence of countable universal graphs
• There is no universal countable random-free graph
• Some remarks on universal graphs

Cites work

• scientific article; zbMATH DE number 3875336 (Why is no real title available?)
• scientific article; zbMATH DE number 3902684 (Why is no real title available?)
• scientific article; zbMATH DE number 3743278 (Why is no real title available?)
• scientific article; zbMATH DE number 48089 (Why is no real title available?)
• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• scientific article; zbMATH DE number 3542459 (Why is no real title available?)
• scientific article; zbMATH DE number 3608079 (Why is no real title available?)
• scientific article; zbMATH DE number 3894002 (Why is no real title available?)
• A problem of Ulam on planar graphs
• Countable Ultrahomogeneous Undirected Graphs
• Embedding Graphs into Colored Graphs
• Model theory
• Notes on combinatorial set theory
• On the problem of finding small subdivision and homomorphism bases for classes of countable graphs
• On universal graphs with forbidden topological subgraphs
• On universal graphs without instances of CH
• Probabilities on finite models
• Simplicial Decompositions: Some New Aspects and Applications
• Some remarks on universal graphs
• Some universal graphs
• Stable graphs
• Superstable graphs
• Sur l'extension aux relations de quelques propriétés des ordres
• The age of a relational structure
• Universal graphs and universal functions
• Universal graphs without large bipartite subgraphs
• Zero-One Laws for Sparse Random Graphs

Cited in

(12)

• Nonexistence of universal graphs without some trees
• Nonuniform complexity classes, decision graphs and homological properties of posets
• Universality vs genericity and \(C_4\)-free graphs
• Universal arrow-free graphs
• Graph cores via universal completability
• Forbidden subgraphs and forbidden substructures
• Universal graphs with a forbidden subgraph: block path solidity
• Universal graphs with forbidden subgraphs and algebraic closure
• On graph classes with minor-universal elements
• scientific article; zbMATH DE number 3954975 (Why is no real title available?)
• There is no universal countable random-free graph
• The complexity of a class of infinite graphs

This page was built for publication: Universal elements and the complexity of certain classes of infinite graphs

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