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 language||English (US)|
|Number of pages||14|
|Journal||Mathematical Proceedings of the Cambridge Philosophical Society|
|State||Published - Jan 1 2019|
All Science Journal Classification (ASJC) codes