On Graphs Which Contain All Sparse Graphs

DOI10.1016/S0304-0208(08)73486-8MaRDI QIDQ3958492zbMATH OpenOpenAlexWikidataFDO

Authors László Babai, Fan Chung, Ron Graham, Joel Spencer, P. Erdős

Publication date 1982

Published in Theory and Practice of Combinatorics - A collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-0208(08)73486-8

zbMATH Keywords

probabilistic methoduniversal graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Recommendations

• Sparse universal graphs
• scientific article; zbMATH DE number 3935064
• Large planar subgraphs in dense graphs
• Maximum planar subgraphs in dense graphs
• An extremal result for subgraphs with few edges

Cited in

(28)

• Induced-universal graphs for graphs with bounded maximum degree
• Über die in Graphen enthaltenen saturierten planaren Graphen
• Maximum planar subgraphs in dense graphs
• Adjacency labeling schemes and induced-universal graphs
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Universality for graphs of bounded degeneracy
• scientific article; zbMATH DE number 125475 (Why is no real title available?)
• Packing topological minors half‐integrally
• Graph product structure for non-minor-closed classes
• On universal hypergraphs
• Universality for graphs with bounded density
• On unavoidable graphs
• Almost-spanning universality in random graphs (extended abstract)
• Perfect Storage Representations for Families of Data Structures
• Shorter Labeling Schemes for Planar Graphs
• Universality, tolerance, chaos and order
• Universal and unavoidable graphs
• Universality of random graphs and rainbow embedding
• Optimal threshold for a random graph to be 2-universal
• A note on universal graphs for spanning trees
• Sparse universal graphs for planarity
• Sparse universal graphs
• Universal geometric graphs
• Almost-spanning universality in random graphs
• Sparse multipartite graphs as partition universal for graphs with bounded degree
• Explicit sparse almost-universal graphs for G (n, kn)
• Every graph is contained in a sparsest possible balanced graph
• Expanders are universal for the class of all spanning trees

This page was built for publication: On Graphs Which Contain All Sparse Graphs

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