Some remarks on universal graphs

DOI10.1016/S0012-365X(98)00339-2MaRDI QIDQ5906404zbMATH OpenOpenAlexFDO

Authors Péter Komjáth

Publication date 30 January 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(98)00339-2

zbMATH Keywords

embeddinguniversal countable graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Review text

\textit{P. Komjáth, A. Mekler} and \textit{J. Pach} [Isr. J. Math. 64, No. 2, 158-168 (1988; Zbl 0672.05074)] claimed that there existed a universal countable \(\{C_3, C_5, C_7, \ldots , C_{2s+1}\}\)-free graph. (Such a graph contains an induced embedding of all countable \(\{C_3, C_5, C_7, \ldots , C_{2s+1}\}\)-free graphs.) The proof given, however, was incorrect. In the paper under review, the auhor provides a correct proof. In addition it is shown that there is no universal countable \(X\)-free graph, where \(X\) is the 5-vertex graph with one vertex of degree 4 and the remainder of degree 2. More generally, there is no universal countable \(H\)-free graph if \(H\) is the disjoint union of 3 or more complete \(n\)-cliques (\(n \geq 2\)) and one vertex joined to every other.

Recommendations

• Some remarks on universal graphs
• Some universal graphs
• Universal graphs and induced-universal graphs
• Existence and nonexistence of universal graphs
• Universal and unavoidable graphs
• Almost universal graphs
• On universal hypergraphs
• Universal graphs and universal permutations
• scientific article; zbMATH DE number 867652
• On the existence of countable universal graphs

Cites work

• Graphs omitting a finite set of cycles
• scientific article; zbMATH DE number 3902684 (Why is no real title available?)
• scientific article; zbMATH DE number 1117459 (Why is no real title available?)
• Nonexistence of universal graphs without some trees
• On the existence of countable universal graphs
• Some universal graphs
• There is no universal countable pentagon‐free graph
• Universal arrow-free graphs
• Universal graphs and universal functions

Cited in

(23)

• Universal arrow-free 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)
• Bowtie-free graphs have a Ramsey lift
• Universality vs genericity and \(C_4\)-free graphs
• Many Facets of Dualities
• A Universal Structure for N -Free Graphs
• Graph cores via universal completability
• scientific article; zbMATH DE number 4170938 (Why is no real title available?)
• The research of the existence of universal hypergraphs
• There is no universal countable pentagon‐free graph
• Extending partial isometries of generalized metric spaces
• AN AXIOMATIC APPROACH TO FREE AMALGAMATION
• A universality theorem for stressable graphs in the plane
• Ramsey properties and extending partial automorphisms for classes of finite structures
• Universal graphs with a forbidden near‐path or 2‐bouquet
• INVARIANT MEASURES CONCENTRATED ON COUNTABLE STRUCTURES
• A note on classes of subgraphs of locally finite graphs
• Bowtie‐free graphs and generic automorphisms
• Conant-independence and generalized free amalgamation
• Universal graphs between a strong limit singular and its power
• Universal graphs with a forbidden subtree

This page was built for publication: Some remarks on universal graphs

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