Extremal density for subdivisions with length or sparsity constraints
Given a graph H , a balanced subdivision of H is obtained by replacing all edges of H with internally disjoint paths of the same length. In this paper, we prove that for any graph H , a linear-in- e ( H ) bound on average degree guarantees a balanced H -subdivision. This strengthens an old result of Bollobás and Thomason, and resolves a question of Gil-Fernández, Hyde, Liu, Pikhurko and Wu. We observe that this linear bound on average degree is best possible whenever H is logarithmically dense. We further show that this logarithmic density is the critical threshold: for many graphs H below this density, its subdivisions are forcible by a sublinear-in- e ( H ) bound on average degree. We provide such examples by proving that the subdivisions of any almost bipartite graph H with sublogarithmic density are forcible by a sublinear-in- e ( H ) bound on average degree, provided that H satisfies some additional separability condition.
Authors
- Fan Yang (ORCID: https://orcid.org/0000-0003-1511-6586)
- Donglei Yang (ORCID: https://orcid.org/0000-0002-4992-6555)
- Jaehoon Kim (ORCID: https://orcid.org/0000-0002-1411-4186)
- Guanghui Wang (ORCID: https://orcid.org/0000-0002-3730-5575)
- Hong Liu (ORCID: https://orcid.org/0000-0002-0863-7853)
- Yantao Tang
Institutions
- Shandong University (CN)
- Georgia State University (US)
- Institute for Basic Science (KR)
- Department of Mathematical Sciences (RU)
Publication Details
- Journal
- Journal of Combinatorial Theory Series B
- Published
- 2025-11-20
- DOI
- https://doi.org/10.1016/j.jctb.2025.11.001
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00