Faithful Universal Graphs for Minor-Closed Classes

Abstract. It was proved by Huynh et al. [ Universality in Minor-Closed Graph Classes, preprint, arXiv:2109.00327, 2021] that any countable graph containing every countable planar graph as a subgraph has an infinite clique minor. We prove a finite, quantitative version of this result: for fixed [Formula: see text], if a graph [Formula: see text] is [Formula: see text]-minor-free and contains every [Formula: see text]-vertex planar graph as a subgraph, then [Formula: see text] has [Formula: see text] vertices. On the other hand, we construct a polynomial size [Formula: see text]-minor-free graph containing every [Formula: see text]-vertex tree as an induced subgraph, and a polynomial size [Formula: see text]-minor-free graph containing every [Formula: see text]-vertex [Formula: see text]-minor-free graph as the induced subgraph. This answers several problems raised recently by Bergold et al. [ Subgraph-universal planar graphs for trees, in Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci., Springer, 2025, pp. 62–75]. We study more generally the order of universal graphs for various classes (of graphs of bounded degree, treedepth, pathwidth, or treewidth) if the universal graphs retain some of the structure of the original class.