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.
|Number of pages||14|
|Journal||Mathematical Proceedings of the Cambridge Philosophical Society|
|Publication status||Published - Jan 2019|