WorksMathematics
You Can Have It All: Small sparse induced-universal graphs for minor-closed classes
Abstract
We show that, for every fixed proper minor-closed graph class and every positive integer , there exists a graph with vertices and edges such that every -vertex graph in is isomorphic to an induced subgraph of . 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 the number of vertices in induced-universal graphs (previously obtained as a corollary of a result of DeVos et al. (J. Comb. Theory, Ser. {B} 2004) and a result of Gavoille and Labourel (ESA 2007)) and the number of edges in subgraph-universal graphs (previously by Babai et al. (Theory and Practice of Combinatorics 1982)).