Optimal induced universal graphs for bounded-degree graphs

Noga Alon, Rajko Nenadov

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

We show that for any constant Δ ≥ 2, there exists a graph Γ with O(n Δ/2 ) vertices which contains every n-vertex graph with maximum degree Δ as an induced subgraph. For odd Δ this significantly improves the best-known earlier bound and is optimal up to a constant factor, as it is known that any such graph must have at least Ω(n Δ/2 ) vertices.

Original languageEnglish
Pages (from-to)61-74
Number of pages14
JournalMathematical Proceedings of the Cambridge Philosophical Society
Volume166
Issue number1
DOIs
Publication statusPublished - Jan 2019

Cite this