Maximum Cuts in H-Free Graphs.

For a graph G, let f(G) be the maximum number of edges in a cut of G. For a positive integer m and a set of graphs H , let f (m , H) be the minimum possible cardinality of f(G), as G ranges over all graphs on m edges which contain no graphs in H . Suppose that r ≥ 8 is an even integer and H = { C 5 , C 6 , ... , C r - 1 } . In this paper, we prove that f (m , H) ≥ m / 2 + c m r r + 1 for some real c > 0 , which improves a result of Alon et al. We also give a general lower bound on f (m , H) when H = { K s + K t ¯ } . This extends a result of Zeng and Hou. [ABSTRACT FROM AUTHOR]