Bipartite Turán number of paths and other trees
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_ | 1866911258208370688 |
|---|---|
| author | Bonamy, Marthe Leclere, Théotime Picavet, Timothé |
| author_facet | Bonamy, Marthe Leclere, Théotime Picavet, Timothé |
| contents | We solve a recent question of Caro, Patkós and Tuza by determining the exact maximum number of edges in a bipartite connected graph as a function of the longest path it contains as a subgraph and of the number of vertices in each side of the bipartition. This was previously known only in the case where both sides of the bipartition have equal size and the longest path has size at most $5$. We also discuss possible generalizations replacing "path" with some specific types of trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_07374 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bipartite Turán number of paths and other trees Bonamy, Marthe Leclere, Théotime Picavet, Timothé Combinatorics Discrete Mathematics We solve a recent question of Caro, Patkós and Tuza by determining the exact maximum number of edges in a bipartite connected graph as a function of the longest path it contains as a subgraph and of the number of vertices in each side of the bipartition. This was previously known only in the case where both sides of the bipartition have equal size and the longest path has size at most $5$. We also discuss possible generalizations replacing "path" with some specific types of trees. |
| title | Bipartite Turán number of paths and other trees |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2511.07374 |