### Maximum cuts of graphs with forbidden cycles

#### Abstract

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*, *C*_{r − 1}) ≥ *m*/2 + *c*(*r*)*m*^{r/(r + 1)} for all *m*. In the present article, we show that *f*(*m*, *C*_{r − 1}) ≥ *m*/2 + *c*(*r*)(*m*^{r}log^{4}*m*)^{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 ℋ = {*K*_{2, s}, *C*_{5}} and ℋ = {*C*_{4}, *C*_{5}, …, *C*_{r − 1}}, both of which improve the results of Alon et al.

#### Keywords

DOI: https://doi.org/10.26493/1855-3974.1218.5ed

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications