betaFeedback

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 G\mathcal{G} and every positive integer nn, there exists a graph UnU_n with n1+o(1)n^{1+o(1)} vertices and edges such that every nn-vertex graph in G\mathcal{G} is isomorphic to an induced subgraph of UnU_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 the number of vertices in induced-universal graphs (previously O(n2)O(n^2) 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 O(n3/2)O(n^{3/2}) by Babai et al. (Theory and Practice of Combinatorics 1982)).

Paper details

vlnc:W_8twddu33
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…