Universal elements and the complexity of certain classes of infinite graphs

DOI10.1016/0012-365X(91)90340-8zbMATH Open0756.05097MaRDI QIDQ1191925FDOQ1191925

János Pach, Péter Komjáth

Publication date: 27 September 1992

Published in: Discrete Mathematics (Search for Journal in Brave)

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

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)

Cites Work

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

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
• On graph classes with minor-universal elements
• Universal graphs with forbidden subgraphs and algebraic closure
• Title not available (Why is that?)
• 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)