Packing subdivisions into regular graphs
Montgomery R, Petrova KH, Ranganathan A, Tan J. Packing subdivisions into regular graphs. arXiv, 2508.00480.
Download (ext.)
Preprint
| Submitted
| English
Author
Montgomery, Richard;
Petrova, Kalina HISTA;
Ranganathan, Arjun;
Tan, Jane
Department
Abstract
We show that, for any graph F and η > 0, there exists a d0 = d0(F, η) such that every nvertex d-regular graph with d ≥ d0 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.
Publishing Year
Date Published
2025-08-01
Journal Title
arXiv
Acknowledgement
Supported by the European Research Council (ERC) under the European Union Horizon 2020 research and innovation programme (grant agreement No. 947978). This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413.
Article Number
2508.00480
IST-REx-ID
Cite this
Montgomery R, Petrova KH, Ranganathan A, Tan J. Packing subdivisions into regular graphs. arXiv. doi:10.48550/arXiv.2508.00480
Montgomery, R., Petrova, K. H., Ranganathan, A., & Tan, J. (n.d.). Packing subdivisions into regular graphs. arXiv. https://doi.org/10.48550/arXiv.2508.00480
Montgomery, Richard, Kalina H Petrova, Arjun Ranganathan, and Jane Tan. “Packing Subdivisions into Regular Graphs.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2508.00480.
R. Montgomery, K. H. Petrova, A. Ranganathan, and J. Tan, “Packing subdivisions into regular graphs,” arXiv. .
Montgomery R, Petrova KH, Ranganathan A, Tan J. Packing subdivisions into regular graphs. arXiv, 2508.00480.
Montgomery, Richard, et al. “Packing Subdivisions into Regular Graphs.” ArXiv, 2508.00480, doi:10.48550/arXiv.2508.00480.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2508.00480
Google Scholar