Maximum cuts of graphs with forbidden cycles

For a graph G, let f(G) denote the maximum number of edges in a bipartite subgraph of G. For an integer m ≥ 1 and for a set ℋ of graphs, let f(m, ℋ) denote the minimum possible cardinality of f(G), as G ranges over all graphs on m edges that contain no member of ℋ as a subgraph. In particular, for a given graph H, we simply write f(m, H) for f(m, ℋ) when ℋ = {H}. Let r > 4 be a fixed even integer. Alon et al. (2003) conjectured that there exists a positive constant c(r) such that f(m, Cr − 1) ≥ m/2 + c(r)mr/(r + 1) for all m. In the present article, we show that f(m, Cr − 1) ≥ m/2 + c(r)(mrlog4m)1/(r + 2) for some positive constant c(r) and all m. For any fixed integer s ≥ 2, we also study the function f(m, ℋ) for ℋ = {K2, s, C5} and ℋ = {C4, C5, …, Cr − 1}, both of which improve the results of Alon et al.