Optimal induced universal graphs for bounded-degree graphs
Optimal induced universal graphs for bounded-degree graphs
We show that for any constant $\Delta \ge 2$, there exists a graph $G$ with $O(n^{\Delta / 2})$ vertices which contains every $n$-vertex graph with maximum degree $\Delta$ as an induced subgraph. For odd $\Delta$ this significantly improves the best-known earlier bound of Esperet et al. and is optimal up …