Universality for graphs of bounded degeneracy

Abstract

Given a family $\mathcal{H}$ of graphs, a graph $G$ is called $\mathcal{H}$-universal if $G$ contains every graph of $\mathcal{H}$ as a subgraph. Following the extensive research on universal graphs of small size for bounded-degree graphs, Alon asked what is the minimum number of edges that a graph must have to be universal for the class of all $n$-vertex graphs that are $D$-degenerate. In this paper, we answer this question up to a factor that is polylogarithmic in $n.$

17 pages