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
|Mathematical Proceedings of the Cambridge Philosophical Society
|Published - Jan 1 2019
All Science Journal Classification (ASJC) codes
- General Mathematics