{"id":"arxiv/2611.14194","url":"https://arxiv.org/abs/2611.14194","tags":["math.CO","cs.DM"],"score":0,"title":"You Can Have It All: Small sparse induced-universal graphs for minor-closed classes","domain":"math.CO","source":"arxiv","authors":["Vida Dujmović","Cyril Gavoille","Gwenaël Joret","Piotr Micek","Pat Morin","David R. Wood"],"reviews":0,"subject":"math.CO","summary":"We show that, for every fixed proper minor-closed graph class $\\mathcal{G}$ and every positive integer $n$, there exists a graph $U_n$ with $n^{1+o(1)}$ vertices and edges such that every $n$-vertex graph in $\\mathcal{G}$ is isomorphic to an induced subgraph of $U_n$. This result generalizes and unifies the results of Dujmović et al. (J. ACM 2021) on induced-universal graphs and the results of Esperet, Joret, and Morin (J. London Math. Soc. 2023) on sparse induced-universal graphs from planar graphs to all proper minor-closed graph classes. It simultaneously improves the previous bounds for…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-10","reactions":{}}