Optimal induced universal graphs for bounded-degree graphs
Lists
Only you see this
Abstract
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 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 Γ 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 Γ isomorphic to H.
BibTeX
@inproceedings{alon2017optimal,
author = {Noga Alon and Rajko Nenadov},
title = {{Optimal induced universal graphs for bounded-degree graphs}},
booktitle = {SODA},
year = {2017},
doi = {10.1137/1.9781611974782.74},
}Loading related content...