Universality for Graphs of Bounded Degeneracy
Peter Allen, Julia Böttcher, Anita Liebenau · Random Structures and Algorithms · 2026
ABSTRACT Given a family of graphs, a graph is called ‐universal if contains every graph of 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 ‐vertex graphs that are ‐degenerate. In this paper, we answer this question up to a factor that is polylogarithmic in .