Turán Numbers of Multiple Paths and Equibipartite Forests

Abstract

The Turán number of a graph H , ex( n, H ), is the maximum number of edges in any graph on n vertices which does not contain H as a subgraph. Let P l denote a path on l vertices, and let k ⋅ P l denote k vertex-disjoint copies of P l . We determine ex( n, k ⋅ P 3 ) for n appropriately large, answering in the positive a conjecture of Gorgol. Further, we determine ex( n, k ⋅ P l ) for arbitrary l , and n appropriately large relative to k and l . We provide some background on the famous Erdős–Sós conjecture, and conditional on its truth we determine ex( n, H ) when H is an equibipartite forest, for appropriately large n .