Faithful universal graphs for minor-closed classes
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913086342955008 |
|---|---|
| author | Bastide, Paul Esperet, Louis Groenland, Carla Hilaire, Claire Rambaud, Clément Wesolek, Alexandra |
| author_facet | Bastide, Paul Esperet, Louis Groenland, Carla Hilaire, Claire Rambaud, Clément Wesolek, Alexandra |
| contents | It was proved by Huynh, Mohar, Šámal, 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^{Ω(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šič, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_19582 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Faithful universal graphs for minor-closed classes Bastide, Paul Esperet, Louis Groenland, Carla Hilaire, Claire Rambaud, Clément Wesolek, Alexandra Combinatorics Data Structures and Algorithms It was proved by Huynh, Mohar, Šámal, 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^{Ω(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šič, 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. |
| title | Faithful universal graphs for minor-closed classes |
| topic | Combinatorics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.19582 |