Pith. sign in

Faithful universal graphs for minor-closed classes

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

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.

fields

math.CO 1

years

2025 1

verdicts

ACCEPT 1

representative citing papers

Smaller universal posets

math.CO · 2025-09-22 · accept · novelty 8.0

Every n-element poset embeds into a poset of size at most 2^(2n/3 + C*sqrt(n)), improving the folklore 2^n upper bound for universal posets.

citing papers explorer

Showing 1 of 1 citing paper.

  • Smaller universal posets math.CO · 2025-09-22 · accept · none · ref 8 · internal anchor

    Every n-element poset embeds into a poset of size at most 2^(2n/3 + C*sqrt(n)), improving the folklore 2^n upper bound for universal posets.