@inproceedings{457aa86ca17f480d9b9e3e7334bedd32,
title = "Optimal induced universal graphs for bounded-degree graphs",
abstract = "We show that for any constant δ ≥ 2, there exists a graph T 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 of Esperet et al. and is optimal up to a constant factor, as it is known that any such graph must have at least (n δ =2) vertices. Our proof builds on the approach of Alon and Capalbo (SODA 2008) together with several additional ingredients. The construction of T is explicit and is based on an appropriately defined composition of high-girth expander graphs. The proof also provides an efficient deterministic procedure for finding, for any given input graph H on n vertices with maximum degree at most Δ, an induced subgraph of T isomorphic to H.",
author = "Noga Alon and Rajko Nenadov",
year = "2017",
month = jan,
day = "1",
doi = "10.1137/1.9781611974782.74",
language = "English (US)",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Association for Computing Machinery",
pages = "1149--1157",
editor = "Klein, {Philip N.}",
booktitle = "28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017",
note = "28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 ; Conference date: 16-01-2017 Through 19-01-2017",
}