Faithful universal graphs for minor-closed classes
By: Paul Bastide , Louis Esperet , Carla Groenland and more
Potential Business Impact:
Makes huge graphs with tiny pieces.
It was proved by Huynh, Mohar, \v{S}\'amal, Thomassen and Wood in 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 $t$, if a graph $G$ is $K_t$-minor-free and contains every $n$-vertex planar graph as a subgraph, then $G$ has $2^{\Omega(n)}$ vertices. On the other hand, we construct a polynomial size $K_4$-minor-free graph containing every $n$-vertex tree as an induced subgraph, and a polynomial size $K_7$-minor-free graph containing every $n$-vertex $K_4$-minor-free graph as induced subgraph. This answers several problems raised recently by Bergold, Ir\v{s}i\v{c}, Lauff, Orthaber, Scheucher and Wesolek. 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.
Similar Papers
Polynomial Bounds for the Graph Minor Structure Theorem
Combinatorics
Makes computers solve hard problems much faster.
Excluding a Forest Induced Minor
Combinatorics
Finds patterns in networks, even when parts are missing.
Induced Minors and Region Intersection Graphs
Combinatorics
Graphs can't always be drawn as overlapping shapes.