MAXIMUM BIPARTITE SUBGRAPHS IN H-FREE GRAPHS

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)) >= 1/2m + 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,K-s. We show that f (m, K-k(')) >= 1/2m + Omega(m((5k-8)/(6k-10))) and f(m,K-t,s(')) >= 1/2m + 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. Bollobas, M. Krivelevich, B. Sudakov (2003).