Bipartite Turán Numbers of Trees and Star Forests

Abstract

The bipartite Turán number of a graph $H$, denoted $\text{ex}(m,n;H)$, is the maximum number of edges in any $H$-free bipartite graph $G=(A,B;E)$ with parts of size $|A|=m$ and $|B|=n$. We study this problem for two families. For a tree $T=T(r,s)$ with parts $R$ and $S$ of sizes $|R|=r\le s=|S|$, we prove \[ (r - 1) n \;\le\; \text{ex}(m, n; T(r, s)) \;\le\; (r - 1) n + O(m) \] for $n$ sufficiently large compared to $m$, $r$, and $s$, determining the leading-order term exactly (with the star case $r=1$ solved with an exact formula). For a star forest $F={\bigcup }_{i=1}^k{S}_{d_i}$ with $d_1\ge \cdots \ge d_k$, we determine the exact value $\text{ex}(m,n;F)=(k-1)n+(d_k-1)(m-k+1)$ for $n$ sufficiently large, and characterize the unique extremal graph.