Czechoslovak Mathematical Journal, Vol. 72, No. 3, pp. 621-635, 2022
Maximum bipartite subgraphs in $H$-free graphs
Jing Lin
Received July 20, 2020. Published online June 3, 2022.
Abstract: Given a graph $G$, let $f(G)$ denote the maximum number of edges in a bipartite subgraph of $G$. Given a fixed graph $H$ and a positive integer $m$, let $f(m,H)$ denote the minimum possible cardinality of $f(G)$, as $G$ ranges over all graphs on $m$ edges that contain no copy of $H$. In this paper we prove that $f(m,\theta_{k,s})\geq\tfrac12 m +\Omega(m^{(2k+1)/(2k+2)})$, which extends the results of N. Alon, M. Krivelevich, B. Sudakov. Write $K'_k$ and $K'_{t,s}$ for the subdivisions of $K_k$ and $K_{t,s}$. We show that $f(m,K'_k)\geq\tfrac12 m +\Omega(m^{(5k-8)/(6k-10)})$ and $f(m,K'_{t,s})\geq\tfrac12 m +\Omega(m^{(5t-1)/(6t-2)})$, improving a result of Q. Zeng, J. Hou. We also give lower bounds on wheel-free graphs. All of these contribute to a conjecture of N. Alon, B. Bollobás, M. Krivelevich, B. Sudakov (2003).
Affiliations: Jing Lin, School of Computer Science and Mathematics, Fujian University of Technology, No. 3 Xueyuan Road, University Town, Minhou, Fuzhou City, Fujian Province 350118, P. R. China, e-mail: sd_frf@163.com
