Maximum bipartite subgraphs in $H$-free graphs

Lin, Jing

Czechoslovak Mathematical Journal, Tome 72 (2022) no. 3, pp. 621-635.

Résumé

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 \tfrac 12 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 \tfrac 12 m +\Omega (m^{(5k-8)/(6k-10)})$ and $f(m,K'_{t,s})\geq \tfrac 12 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).

Détail

DOI : 10.21136/CMJ.2022.0302-20

Classification : 05C35, 05C70
Keywords: bipartite subgraph; $H$-free; partition