Universal elements and the complexity of certain classes of infinite graphs
type: Item
instance of: scholarly article
title: Universal elements and the complexity of certain classes of infinite graphs
zbMATH Open document ID: 0756.05097
DOI: 10.1016/0012-365X(91)90340-8
author: János Pach
author: Péter Komjáth
published in: Discrete Mathematics
publication date: 1992-09-27T00:00:00Z
review text: A class of graphs is said to have a universal element \(G\) if every other element of the class is isomorphic to an induced subgraph of \(G\). The authors give a survey of some recent developments in the topic in the following areas: (1) graphs universal for isometric embeddings, (2) universal random graphs, (3) universal graphs with forbidden subgraphs, and (4) same with forbidden topological subgraphs. A new measure of complexity of a class with universal element is introduced and investigated. Finally, some analogous questions for hypergraphs are considered.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 63139
zbMATH Keywords: induced subgraph
zbMATH Keywords: universal element
zbMATH Keywords: isometric embeddings
zbMATH Keywords: random graphs
zbMATH Keywords: hypergraphs
reviewed by: Jozef Širáň
MaRDI profile type: Publication
cites work: The age of a relational structure
cites work: Model theory
cites work: Q5186348
cites work: On universal graphs with forbidden topological subgraphs
cites work: On the problem of finding small subdivision and homomorphism bases for classes of countable graphs
cites work: Q3999150
cites work: Some remarks on universal graphs
cites work: Q4065548
cites work: Probabilities on finite models
cites work: Sur l'extension aux relations de quelques propriétés des ordres
cites work: Q3929755
cites work: Q4117857
cites work: Simplicial Decompositions: Some New Aspects and Applications
cites work: Q3342616
cites work: Embedding Graphs into Colored Graphs
cites work: Superstable graphs
cites work: Q3680856
cites work: Some universal graphs
cites work: Universal graphs without large bipartite subgraphs
cites work: Countable Ultrahomogeneous Undirected Graphs
cites work: Q4173397
cites work: A problem of Ulam on planar graphs
cites work: Stable graphs
cites work: Universal graphs and universal functions
cites work: Notes on combinatorial set theory
cites work: On universal graphs without instances of CH
cites work: Zero-One Laws for Sparse Random Graphs
description: scientific article; zbMATH DE number 63139