Packing subdivisions into regular graphs
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_ | 1866910013700702208 |
|---|---|
| author | Montgomery, Richard Petrova, Kalina Ranganathan, Arjun Tan, Jane |
| author_facet | Montgomery, Richard Petrova, Kalina Ranganathan, Arjun Tan, Jane |
| contents | We show that, for any graph $F$ and $η>0$, there exists a $d_0=d_0(F,η)$ such that every $n$-vertex $d$-regular graph with $d \geq d_0$ has a collection of vertex-disjoint $F$-subdivisions covering at least $(1-η)n$ vertices. This verifies a conjecture of Verstraëte from 2002 and improves a recent result of Letzter, Methuku and Sudakov which additionally required $d$ to be at least polylogarithmic in $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_00480 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Packing subdivisions into regular graphs Montgomery, Richard Petrova, Kalina Ranganathan, Arjun Tan, Jane Combinatorics 05C60, 05C35 We show that, for any graph $F$ and $η>0$, there exists a $d_0=d_0(F,η)$ such that every $n$-vertex $d$-regular graph with $d \geq d_0$ has a collection of vertex-disjoint $F$-subdivisions covering at least $(1-η)n$ vertices. This verifies a conjecture of Verstraëte from 2002 and improves a recent result of Letzter, Methuku and Sudakov which additionally required $d$ to be at least polylogarithmic in $n$. |
| title | Packing subdivisions into regular graphs |
| topic | Combinatorics 05C60, 05C35 |
| url | https://arxiv.org/abs/2508.00480 |