Turán number of complete bipartite graphs with bounded matching number

Abstract

Let $\mathcal{F}$ be a family of graphs. A graph $G$ is $\mathcal{F}$-free if $G$ does not contain any $F\in \mathcal{F}$ as a subgraph. The Turán number $ex(n,\mathcal{F})$ is the maximum number of edges in an $n$-vertex $\mathcal{F}$-free graph. Let $M_s$ be the matching consisting of $s$ independent edges. Recently, Alon and Frank determined the exact value of $ex(n,\{K_m,M_{s+1}\})$. Gerbner obtained several results about $ex(n,\{F,M_{s+1}\})$ when $F$ satisfies certain proportions. In this paper, we determine the exact value of $ex(n,\{K_{l,t},M_{s+1}\})$ when $s,n$ are large enough for every $3\le l\le t$. When $n$ is large enough, we also show that $ex(n,\{K_{2,2},M_{s+1}\})=n+\left(\genfrac{}{}{0ex}{}{s}{2}\right)-\lceil \frac{s}{2}\rceil$ for $s\ge 12$ and $ex(n,\{K_{2,t},M_{s+1}\})=n+(t-1)\left(\genfrac{}{}{0ex}{}{s}{2}\right)-\lceil \frac{s}{2}\rceil$ when $t\ge 3$ and $s$ is large enough.

15 pages, 2 figures