ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 15 (2018) 147-160 https://doi.org/10.26493/1855-3974.1218.5ed (Also available at http://amc-journal.eu) Maximum cuts of graphs with forbidden cycles* Qinghou Zeng School of Mathematical Sciences, University of Science and Technology of China, Hefei, Anhui, P. R. China, and Center for Discrete Mathematics, Fuzhou University, Fuzhou, Fujian, P. R. China Jianfeng Hou f Center for Discrete Mathematics, Fuzhou University, Fuzhou, Fujian, P. R. China Received 18 October 2016, accepted 2 November 2017, published online 13 June 2018 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 H of graphs, let f (m, H) denote the minimum possible cardinality of f (G), as G ranges over all graphs on m edges that contain no member of H as a subgraph. In particular, for a given graph H, we simply write f (m, H) for f (m, H) when H = {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_i) > 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)(mr log4 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, H) for H = {K2,s, C5} and H = {C4, C5,..., Cr-1}, both of which improve the results of Alon et al. Keywords: H-free graph, partition, maximum cut. Math. Subj. Class.: 05C35, 05C70 1 Introduction All graphs considered here are finite, undirected and have no loops and no parallel edges, unless otherwise specified. All logarithms in this paper are with the natural base e. For a graph G, let f (G) denote the maximum number of edges in a cut of G, that is, the *This work is supported by NSFC (Grant No. 11671087). The authors are indebted to the anonymous referees for many valuable comments and constructive suggestions. Qinghou Zeng would like to thank his advisors Genghua Fan and Jianfeng Hou for getting him interested in graph theory. t Corresponding author. E-mail addresses: zengqh@ustc.edu.cn (Qinghou Zeng), jfhou@fzu.edu.cn (Jianfeng Hou) Abstract ©® This work is licensed under https://creativecommons.org/licenses/by/3.0/ 148 Ars Math. Contemp. 15 (2018) 147-160 maximum number of edges in a bipartite subgraph of G. For an integer m, let f (m) denote the minimum value of f (G), as G ranges over all graphs with m edges. Thus, f (m) is the largest integer f such that any graph with m edges contains a bipartite subgraph with at least f edges. It is easy to show that f (m) > m/2 by considering a random bipartition of a graph with m edges. Edwards [10, 11] proved that for every m f (m) > m + 4(V2m +4 - 2) ' (U) and noticed that this is tight when m = (2) for odd integers k. For more information on f (m) and some related topics, we refer the reader to [1, 3, 5,6,8,14,15,16,21,26,27,28]. For survey articles, see [7, 23]. Suppose that H is a set of graphs. Let f (m, H) denote the minimum possible cardinality of f (G), as G ranges over all graphs on m edges that contain no member of H. In particular, for a given graph H, we simply write f (m, H) for f (m, H) when H = {H}. It is noted (see, e.g., [2]) that for every fixed graph H there exist positive constants e = e(H) and c = c(H) such that f (m, H) > m/2 + cm1/2+e for all m. However, the problem of estimating the error term more precisely is not easy, even for relatively simple graphs H. For example, let r > 4 be an integer and let H be the cycle Cr-1. The case r = 4 has been studied extensively. After a series of papers by various researchers [12, 22, 24], Alon [1] proved that f (m, C3) = m/2 + ©(m4/5) for all m. For general r > 4, Alon et al. [4] proposed the following conjecture. Conjecture 1.1. For every integer r > 4, there is a positive constant c(r) such that f (m, Cr_i) > m + c(r)m^ (1.2) for all m. This is tight, up to the value of c(r), for all r > 4. The authors confirmed (1.2) for all odd r > 4. In this paper, we consider the conjecture for every even integer r > 4 and establish the following theorem. Theorem 1.2. For every even integer r > 4, there is a positive constant c(r) such that f (m,Cr-1) > m + c(r) (mr log4 m) ^ for all m. Alon et al. [4] also studied the function f (m, H) when H is the complete bipartite graph K2,s. It is proved that, for every s > 2, there is a positive constant c(s) such that f(m,K2,s) > m + c(s)m5/6 for all m, and this is tight up to the value of c(s). Now, we consider the function f (m, H) for H = {K2,s, C5}, which improves the above lower bound as follows. Theorem 1.3. For each s > 2, let G be a {K2,s, C5}-free graph with m edges. Then there exists a positive constant c(s) such that f(G) > m + c(s)m6/7 for all m. Q. Zeng and J. Hou: Maximum cuts of graphs with forbidden cycles 149 Moreover, Alon et al. [2] considered the function f (m, H) for H = {C3,..., Cr-1}, and proved that f (m, H) > + c(r)m for all m. In the following, we allow the occurence of triangles and get a stronger result. Theorem 1.4. Let r > 4 be a fixed even integer and Hr = {C4,..., Cr-1}. Then there exists a positive constant c(r) such that f (m, Hr) > m + c(r)m^fr for all m. 2 Maximum cuts of C2k+1-free graphs In this section, we give a proof of Theorem 1.2. The goal is to prove that the chromatic number of a C2k+1-free graph is relatively small, since graphs with small chromatic number must have large bipartite subgraphs. For a graph G, let x(G) and a(G) denote the chromatic number and independence number of G, respectively. We need the following lemma, whose easy proof can be found in [1] (see also [2, 12, 21]). Lemma 2.1. Let G be a graph with m edges and chromatic number at most x. Then f (G) > m. 2X To find an upper bound on the chromatic number of a C2k+1-free graph, we require a lemma of Jensen and Toft [17] (see also [18]), which is a general lemma on monotone properties. Note that a graph property is called monotone if it holds for all subgraphs of a graph which has this property, i.e., is preserved under deletion of edges and vertices. Lemma 2.2 (Jensen and Toft [17, §7.3]). For s > 1, let ^: [s, to) ^ (0, to) be a positive continuous non-decreasing function. Suppose that P is a family of graphs with monotone properties such that a(G) > ^(\V (G)|) for every G G P with \V (G)| > s. Then for every such G with \V(G)\ > s, r |V(G)| x x(G) < s + / -— dx. Js ^(x) In order to bound x(G) by Lemma 2.2, we need bound a(G) of a C2k+1-free graph G in terms of \V(G)\. The following well-known Turan's lower bound (see, e.g., [25]) and another two lemmas from [19] and [20] will be used to bound a(G). Lemma 2.3 (Turan's Lower Bound). Let G be a graph on n vertices with average degree at most d. Then n a(G) > TTd- Lemma 2.4 (Li et al. [19]). Let G be a graph on n vertices with average degree at most d. If the average degree of the subgraph induced by the neighborhood of any vertex is at most a, then a(G) > nFa+1(d), 150 Ars Math. Contemp. 15 (2018) 147-160 where rw n f1 (1 - t)1/a , log(x/a) - 1 , Fa(x) = (, - ) u dt > g( 1 )-, (x > 0). Jo a + (x — a)t x Lemma 2.5 (Li and Zang [20]). For a fixed integer k > 2, let G be a C2k+1-free graph with degree sequence d1,d2,... ,dn. Then 1 -L. ^ k—1 ' x v 1 k — 1 "(G) > ^ 1)' i=1 Next, we shall also use the following upper bound, proved by Erdos and Gallai [13], on the maximum number of edges in Pt-free graphs, where Pt stands for a simple path with t vertices. Lemma 2.6 (Erdos and Gallai [13]). Let G be a Pt+1-free graph with n vertices. Then G contains at most (t — 1)n/2 edges. Finally, we give a simple inequality, which is used frequently in our proofs of the following several theorems. We omit the proof details. Lemma 2.7. For any real number x > 0,we have x > max j log(x + 3) — — ,e log x^ (2.1) and that the function g(x) = log x/x is monotonically increasing over the interval (0, e] and decreasing over the interval (e, ). Having finished all the necessary preparations, we are ready to give lower bounds of the independence number of a C2fc+1-free graph. Theorem 2.8. For any fixed integer k > 2, let G = (V, E) be a C2k+1-free graph on n vertices with average degree at most d. Then ^ (nlog d 1 . 1 a(G) > max{-^-^, —(nk logn) . Proof. First, we prove that n log d a(G) > W. Case 1. d < e2(2k — 1). By inequality (2.1), we have 5 , , 1 log d (1 + d) log d 2k > log(2k — 1) + - > log d + - > log d + -2- = v ; s . 2 e d d This together with Lemma 2.3 implies that n n log d a(G) > TTd > "2k^. Case 2. d> e2(2k — 1). It follows from inequality (2.1) that 2k — 1 > 1 + log(2k — 1). This together with d > e2(2k — 1) yields that 2k log d > 2 + log(2k — 1) > --- (1 + log(2k — 1)), 2k 1 Q. Zeng and J. Hou: Maximum cuts of graphs with forbidden cycles 151 which gives that log d - (l+log(2k - 1)) > iOgp (2.2) Since G is C2k+1-free, the subgraph induced by the neighborhood of any vertex of G is P2k-free. By Lemma 2.6, the average degree of any P2k-free graph is at most 2(k - 1). It follows from Lemma 2.4 and inequality (2.2) that TT f,n ^ nl0g e(2fc-i) ^ nlogd a(G) > nF2k-i(d) > --- > d - 2kd ' as desired. Now, we show that *(G) > TTÖ log n) . 5k2 Let vi,... ,vn be the vertices of G such that d(v.) = d. for 1 < i < n. Set S = { v. € V : di > (n logk n) k+r j. If |S| > 2n/5, then, by Lemma 2.5, we have 1 n r k-l i 2 fc-l I a(G) > E dr) k > i • (n logfc n) ^ k > (nk log n) ^. i=i Suppose that |S| < 2n/5. Consider the graph H induced by V\S. Clearly, the number of vertices contained in H is at least 3n/5, and the average degree d(H) of H is at most (n logk n)l/(k+l). If d(H) < e, then the desired result follows immediately from Lemma 2.3. Otherwise, by the preceding result, we obtain ^ / tt\ ___ 3n log d(H) 1 . a(G) > a(H) > 35- • -2^ > (nk log n) , where the last inequality holds because the function g(x) = log x/x is monotonically decreasing over the interval [e, (n logk n)l/(k+l)] by Lemma 2.7. This completes the proof of Theorem 2.8. □ With the help of Lemma 2.2 and Theorem 2.8, we establish the following theorem, which plays a key role in our proof of Theorem 1.2. The approach we take is an extension of that by Poljak and Tuza [22]. Theorem 2.9. For any fixed integer k > 2, let G be a C2k+l-free graph with m > 1 edges. Then i \3 ( m \ k+2 x(G) < 32(k +1) .—j log m Proof. Let G be a C2k+l-free graph on n vertices with m > 1 edges. If G is bipartite, then x(G) = 2 and the claim follows. Suppose that x(G) > 3. Without loss of generality, we may assume that G is vertex-critical. Note that each vertex-critical graph has minimal degree at least x(G) - 1. It follows that the minimal degree of G is at least 2. Thus, we have m > n. Now, we end the proof by showing the following series of claims. 152 Ars Math. Contemp. 15 (2018) 147-160 i x(G) < 15k3' " ^ Claim 1. X(G) < 15k3/ vlog Uj This is trivial for u < e2 as x(G) < u < e2, hence we may assume that u > e2. For x > e2, define the functions Y(x) = 1 — log-1 x and ^(x) = -^-(xfc log x) k+r. 5k2 Clearly, y(x) > 1/2 for x > e2, and y(x), ^(x) are positive continuous and non-decreasing. By Theorem 2.8, we have a(G) > ^(n). Thus, Lemma 2.2 gives that n 1 — - 5k2 r Y(x) dx n 1 ^ 1 , q / n \ k+T < 15k3' * + Vlog n i'n 1 5k2 f X(G) < e2 + —— dx < e2 + t ^ Hx) Y(e2 ) ./e2 (xk log x) k+T = e2 + 10k2 n*. Otherwise, assume that n < n*. By Lemma 2.7, we know the function g(x) = x/ log x is monotonically increasing over the interval (e, to) and log x > e log log x for each x > 1. Note that m > 1 (which implies n > 3 > e). It follows from Claim 1 that ( ) 1 ( ) 1 ( ) 1 Xo according to the following procedure, which we will call the G algorithm. Set i = 0, G0 = G and n0 = |V(G0)|. Repeat the following steps until ni < n*. • Choose Si to be a maximum independent set of Gj. • Set Gi+1 = Gi\Si andni = |V(Gi)|. Increment i. Let I +1 be the length of the resulting sequence G. By the G algorithm, we immediately have n < n* and that G can be colored by at most x(G^) + I colors. Clearly, we may assume that Ge is vertex-critical. Thus, by Claim 1, for u > 3, we have ( ) 1 ( ) 1 ( ) 1 X(G,) < 15k3 () kTT < 15k3 () kTT < 32k3 (-m-) kT2. (2.3) Vlogn^/ Vlog nv Mog2 m/ Note that x(G^) clearly satisfies the above inequality for u < 2. In the following, we aim to bound the value of Q. Zeng and J. Hou: Maximum cuts of graphs with forbidden cycles 153 Firstly, we give a lower bound of |S^. Let t = 1. It follows from Claim 2 that t — 2. Let I = {0,1,..., I - 1} and J = {2,3,..., t}. Note that n > n* — n/t for each i e I by the G algorithm and the definition of t. Let v 1,..., vn0 be a labelling of the vertices of G0 such that Si = {vp : ni+1 < p _ n4} for each i e I. Denote S the union of Si for all i e I. Thus, for each j e J, we can define {n n ^ ( n ^ Vp G S : -

-j. j j - u j L j Note that S\S£_i C ujejVj C S and I2 C I3 C ... C It. Therefore, for each x e Vj, there exists an i e Ij such that x e Si. In addition, we have V l< Claim 3. For each i G Ij = 0, n - - - - (2.4) 2 1 2 jm n2 log —— |Si| — g2 n . 4fcj2m Let di denote the average degree of Gi for each i e I. Clearly, for each i e Ij, we have di _ 2m _ 2jnm. Suppose that di > e. Recall that the function g(x) = log x/x is decreasing over the interval (e, to). By Theorem 2.8, we have niiogdi > n2 log ^ 1 i| - 2kdi - 4kj2m . Otherwise, di _ e. It follows from Lemma 2.3 that |Si| — nk - 2nj, which together with the fact that x > log x implies the required result as well. This completes the proof of Claim 3. Then, for each x e Si and i e I, define w(x) = |Si | 1. Therefore, for each x e Si and i e Ij , it follows from Claim 3 that 1 4kj 2m 4kj2 mn-2 w(x) =|Si|- _ n^iop-m _ log j + iogm. By the definition of w(x) and the above inequality, we immediately have * -1= E E w(x) ie/\{£-1> xeSi 4kj2|Vj|mn-2 ^^ 16kmn-1 w(x) _ Z^ iog j + iog m _ Z^ iog j + iog m . (2.5) 4kj2|Vj|mn 2 ^^ 16kmn 1 PV . 2 iog j+iog mm _ ^ iog j+iog m' jGJ xEVj j=2 n j=2 n The last inequality follows from (2.4) and the fact j — 2. Finally, we give the following upper bound of Claim 4. t - 1 < 64(k +1)2( ™ ) k+2. v log m / n 154 Ars Math. Contemp. 15 (2018) 147-160 By the definition of n*, we have — ■ — = — = (m logk m) k+2. (2.6) n* n n* i It follows that max{m/n, n/n*} > m2(k+2>, and then i m n ^ 1 maxllog nlog w > 2^log m. (2.7) Suppose that n/n* < m/n. Note that t — 1 < n/n* by the definition of t. Then, we delete the first term of the denominator of (2.5) and obtain ^^ 16kmn-1 16k(t — 1)m 16km RA12( m ) - - log mm - n log mm < n* log mm - v log2 m , where the last inequality follows from (2.6) and (2.7); as desired. Otherwise, n/n* > m/n. Recall that t — 1 < n/n* - t. It follows that f* 1 , 2(t — 1) 2n --dx - -i--—---. J2 log x log t n* log ^T Deleting the second term of the denominator in (2.5), we have „ 16km v^ 1 16km f* 1 , 32km m ) k+2 i — 1 - -V--- --dx - —--- - 64(k + 1)2' ^ + n log j n log x n* log j=2 n ^ logj ~ n ,/2 logx™ " n* log ^Tr " ' "' Vlog2 m Again, the last inequality follows from (2.6) and (2.7). This completes the proof of Claim 4. Now, it follows from (2.3) and Claim 4 that 1 x(G) - x(G,) + i - (32k3 + 64(k + 1)2) k+2 + 1 log m log2 m - 32(k + 1)3(2 1 k + 2 log2 m Thus, we get the desired result and complete the proof of Theorem 2.9. □ We are now in a position to establish Theorem 1.2. Proof of Theorem 1.2. Let r > 4 be a fixed integer and let G be a Cr-1-free graph with m edges. The desired result follows immediately for m =1. Suppose that m > 1. Set r — 1 = 2k + 1 and c(r) = 1/(8r3). By Theorem 2.9, we have 2 2X(G) - 8r3 (-m-) r+2. log2 m This together with Lemma 2.1 yields that mm 1 f (G) > y + c(r) (mr log4 m) r+2. Thus, we complete the proof of Theorem 1.2. □ Q. Zeng and J. Hou: Maximum cuts of graphs with forbidden cycles 155 3 Maximum cuts of H-free graphs In this section, we obtain lower bounds on the size of the maximum cuts of H-free graphs. Let G = (V,, E) be a graph. For a subset U c V, denote E(U) the set of edges of G spanned by U. We need the following simple lemma from [1,4, 8]. Lemma 3.1. Let G = (V, E) be a graph with m edges. Suppose that U c V and let G' be the induced subgraph of G on U. If G' has m' edges, then f (G) > f (G') + . Next, we need another result from [4], which provides a very useful lower bound on the size of a maximum cut in an H-free graph for a certain class of graphs H. Lemma 3.2 (Alon et al. [4]). There exists an absolute positive constant e such that for every positive constant C there is a S = 5(C) > 0 with the following property. Let G be a graph with n vertices (with positive degrees), m edges, and degree sequence d1,d2,... ,dn. Suppose, further, that the induced subgraph on any set of d > C vertices, all of which have a common neighbour, contains at most ed3/2 edges. Then n f (G) > 2 + S . i=1 A graph is r-degenerate if every one of its subgraphs contains a vertex of degree at most r. We need the following easy and well-known fact. See, e.g., [1, 2, 4] for a proof. Lemma 3.3. Let H be an r-degenerate graph on h vertices. Then there is an ordering v1,... ,vh of the vertices of H such that for every 1 < i < h the vertex vi has at most r neighbours vj with j < i. Finally, we shall also use the following lower bound in extremal set theory, proved by Corradi [9], on the size of a set Q from which we can draw N subsets of size at least q such that any two of them share at most A elements. Lemma 3.4 (Corradi [9]). Let Q1,... ,QN be N sets with |Qi | > q for each i = 1,..., N, and let Q be their union. If |Qi n Qj | < A for all i = j, then q2N IQI> qN q + (N - 1)A' Having finished all the necessary preparations, we are ready to give proofs of Theorems 1.3 and 1.4. Our proofs combine combinatorial and probabilistic techniques, including extensions of ideas that appear in [1, 2, 4]. Proof of Theorem 1.3. For each s > 2, let G = (V, E) be a {K2,s, C5}-free graph on n vertices with m edges. Define I = |_4sm2/7J. The proof proceeds by considering two possible cases depending on the existence of dense subgraphs in G. Case 1. G is (£ - 1)-degenerate, that is, it contains no subgraph with minimum degree at least I. In this case, we use Lemma 3.2 to bound f (G). By Lemma 3.3, we can get a 156 Ars Math. Contemp. 15 (2018) 147-160 labelling vi, v2,..., vn of the vertices of G such that d+ < I for every i, where d+ denotes the number of neighbors vj of v. with j < i. Note that J2n=1 d+ = m. Let d. be the degree of vj for each 1 < i < n. Then n n--J+ -i E ^ > E ^ * m6" j=1 j=1 v v Now, we check the condition of Lemma 3.2. For each v G V, let N(v) be the neighborhood of v in G and Nd(v) be any subset of cardinality d of N(v). Denote Gd the subgraph induced by Nd(v). Since G is C5-free, we know that Gvd contains no path of length 3. It follows from Lemma 2.6 that Gvd contains at most d edges, which is smaller than ed3/2 for all d > e-2. Thus, by Lemma 3.2, we have / (G) > * ± ^ > m+2^, j=1 where * = *(e) is a constant, as required. Case 2. There exists a subset Q of q vertices of G such that the induced subgraph G[Q] has minimum degree at least i. Now, we prove that Q contains a subset Q' such that the induced subgraph G[Q'] spans at least qi/4 edges and is 3t-colorable for t = |"4sq/i2]. For fixed x G Q, denote by S(x) the set of vertices in Q which are at distance exactly 2 from x and denote by sx the size of S(x). We bound sx by Lemma 3.4. Claim 5. sx > i2/(2s) for each x G Q. For each x G Q, let Nq (x) be the neighborhood of x in G[Q]. For each v G Nq (x), let Qv = Nq(v) n S(x) . Since G is K2,s-free, we conclude that |Qu n Qv| < s - 1 for each pair of vertices u, v G Nq(x) and that v is adjacent to at most s - 1 vertices in Nq (x). It follows that |Qv | > i - (s - 1) - 1 = i - s. Note that S(x) = (J Qv vENq(x) and |NQ(x)| > ^ > 4s. By Lemma 3.4, we obtain U Qv vENq(x) > _ — s) + (|Nq(x)| — 1)(s - 1) > 2s. '- s)2|nq(x) This completes the proof of Claim 5. sx Let T be a random subset of Q obtained by picking uniformly at random, with repetitions, t vertices of Q. Let Q' be the set of all vertices x in Q such that S(x) n T = 0 and let G[Q'] be the induced subgraph of G on Q'. Claim 6. There exists a set T such that G[Q'] spans at least qi/4 edges. By the definition of Q', for each x G Q, we have Q. Zeng and J. Hou: Maximum cuts of graphs with forbidden cycles 157 where the second inequality follows from Claim 5, and the last inequality holds by noting that t - 4sq/t2. Thus, for each edge xy G E(Q), we obtain P(xy G E(Q')) = P(x G Q') • P(y G Q') > (l - 1) • (l - 4) > 1. By linearity of expectation, and noting that |E (Q)| > qt/2, we have ll P(xy G E(Q')) > ' xy€E(Q) E(|E(Q')|) = £ P(xy G E(Q')) > -|E(Q)| > -qt. Hence, there exists a set T of at most t vertices so that the corresponding graph G[Q'] has at least qf/4 edges. Thus, we complete the proof of Claim 6. Fix such sets T and Q', let G' = G[Q'] and T = {ui,..., uv}, where 1 < t' < t. Now we show G' is 3t-colorable. Define a coloring c of G' in t' colors by coloring each vertex x G Q' with the smallest index of a vertex from T which belongs to S(x). For each 1 < i < t', let Hi be the subgraph of G' induced by the vertices of Q' with color i. Claim 7. For each 1 < i < t', Hi is 3-colorable. For each ui G T and v G N(ui), let HV be the subgraph induced by the neighbors of v with color i in G'. By the above definition and the fact that G is C5-free, we have the following properties: • For each v G N(ui), HV is P4-free; • For each v1, v2 G N(ui) and u G V(HV1) n V(HiV2), u is an isolated vertex in both HV1 and HV-; • For each x G V(H^1) and y G V(HiV2), x and y are nonadjacent in Hi. Note that Hi is induced by the union of V(HV) over all v G N(ui). This together with the above three properties implies that Hi is P4-free, i.e., 3-colorable. Thus, we complete the proof of Claim 7. By the definition of c and Claim 7, we conclude that G' is 3t-colorable. According to Lemma 2.1, it follows that f(GO > |E(Q')| + |E(Q')U |E(Q')| + qt f ( ) " 2 + 6t " 2 + 24 4sq I2" ^ |E(Q')| + |E(Q')| + m6/7 - 2 + 144s - 2+9 . The second inequality follows from Claim 6, and the third inequality holds because q -sx - t2/(2s) by Claim 5. The above inequality together with Lemma 3.1 gives that f(G) - m -|E(Q')| + "EMI + 4s!m6/r = m + 4s!m6/r. JK ' > 2 2 9 2 9 Therefore, the desired result follows immediately from Cases 1 and 2 by setting c(s) = min{ , 4|- }, completing the proof of Theorem 1.3. □ i 158 Ars Math. Contemp. 15 (2018) 147-160 The proof of Theorem 1.4 is similar to that of Theorem 1.3. Proof of Theorem 1.4. Let G be an Hr -free graph on n vertices with m edges. Define ¿ = |_2m2/(r+1)J and proceed as before, by considering two possible cases. Case 1. G contains no subgraph with minimum degree at least In this case, we proceed as in the previous proof. Similarly, the induced subgraph of G on any set of common neighbors of a vertex can span only a linear number of edges, as it contains no copy of C4. Thus, we can apply, again, Lemma 3.2 and conclude, as in the proof of Theorem 1.3, that ^ m m m 5 f (G) >--+ 5>--+ -m r+1, f () > 2+V2I > 2+2 , where 5 = 5(e) is also a constant, as needed. Case 2. There exists a subset Q of q vertices of G such that the induced subgraph G[Q] has minimum degree at least 2£ Here, too, we prove that there exists Q' c Q such that the induced subgraph G[Q'] spans at least q^/2 edges and is 2t-colorable for t = [q/^fc]. Let r = 2k + 2. Denote by Sk (x) the set of vertices in Q which are at distance exactly k from x and denote by sx the size of Sk(x). Since the minimal degree of G[Q] is at least 2^ and G[Q] contains no cycle of length from 4 to 2k + 1, it can easily be seen that sx > 2^(2^ - 2)k-1 > 2^fc for each x G Q. Let T be a random subset of Q obtained by picking, with repetitions, t vertices of Q, each chosen randomly with uniform probability. This together with the fact sx > 2^fc yields that the probability that Sk(x) n T is empty is at most sx\ , 2^fc\« , ( 2^fct l 1 1 - i) — I1 - TJ -/< 4 An argument similar to the one used in the proof of Claim 6, the details of which we omit, shows that there exists a set T of at most t vertices so that the corresponding graph G[Q'] has at least q^/2 edges. Fix such sets T and Q'. Now, we define a coloring c of G' and the induced subgraphs Hi of G' for 1 — i — |T| as in the proof of Theorem 1.3. Claim 8. For each 1 — i — |T |, Hi is the disjoint union of edges modulo isolated vertices. For fixed ui G T and for each v G Sk_1(ui), let HV be the subgraph induced by the neighbors of v with color i in G'. By the above definition, and recalling that G contains no cycle of length from 4 to 2k + 1, we have the following properties: (i) for each v G Sfc_i(ui), HV is P3-free; (ii) for each vi, V2 G Sfc_i(ui), V(Hf) n V(Hf) = 0; (iii) for each x G V(H^1) and y G V(H^2), x and y are nonadjacent in Hi. It follows from (ii) and (iii) that Hi is the disjoint union of HV over all v G Sk_1(ui). Thus, by (i), Hi is the disjoint union of edges modulo isolated vertices. This completes the proof of Claim 8. By the definition of c and Claim 8, we know that G' is 2t-colorable. Using Lemma 2.1, we conclude that |E(Q')| , |E(Q')| |E(Q')| , q^ r q f (G') > ' n + ' ^ n > ' n + — f () > 2 + 4t > 2 +8 ¿k |E (Q')| + ¿k+1 |E(Q')| + (\/2)r Q. Zeng and J. Hou: Maximum cuts of graphs with forbidden cycles 159 The second inequality follows from the fact |E (Q')| > qi/2, and the third inequality holds because q > sx > 2ik. Taking Lemma 3.1 into consideration, we obtain f(G)> m - |E(Q')| + |E(Q')| + (V2)r _r_ m + (V2)r f(G) >-2-+ ""T" + mr+ =12+~L2Tmr+1. Again, we get the required result from Cases 1 and 2 by choosing c(s) = min{2, }, which completes the proof of Theorem 1.4. □ References [1] N. Alon, Bipartite subgraphs, Combinatorica 16 (1996), 301-311, doi:10.1007/bf01261315. [2] N. Alon, B. Bollobas, M. Krivelevich and B. Sudakov, Maximum cuts and judicious partitions in graphs without short cycles, J. Comb. Theory Ser. B 88 (2003), 329-346, doi: 10.1016/s0095-8956(03)00036-4. [3] N. Alon and E. Halperin, Bipartite subgraphs of integer weighted graphs, Discrete Math. 181 (1998), 19-29, doi:10.1016/s0012-365x(97)00041-1. [4] N. Alon, M. Krivelevich and B. Sudakov, MaxCut in H-free graphs, Combin. Probab. Comput. 14 (2005), 629-647, doi:10.1017/s0963548305007017. [5] B. Bollobas and A. D. Scott, Exact bounds for judicious partitions of graphs, Combinatorica 19 (1999), 473-486, doi:10.1007/s004939970002. [6] B. Bollobas and A. D. Scott, Better bounds for Max Cut, in: B. Bollobas (ed.), Contemporary Combinatorics, Janos Bolyai Mathematical Society, Budapest, volume 10 of Bolyai Society Mathematical Studies, pp. 185-246, 2002. [7] B. Bollobas and A. D. Scott, Problems and results on judicious partitions, Random Struct. Algor. 21 (2002), 414-430, doi:10.1002/rsa.10062. [8] B. Bollobas and A. D. Scott, Max fc-cut and judicious fc-partitions, Discrete Math. 310 (2010), 2126-2139, doi:10.1016/j.disc.2010.04.004. [9] K. Corradi, Problem at Schweitzer competition, Mat. Lapok 20 (1969), 159-162, http:// real-j.mtak.hu/9 3 67/. [10] C. S. Edwards, Some extremal properties of bipartite subgraphs, Canad. J. Math. 25 (1973), 475-485, doi:10.4153/cjm-1973-048-x. [11] C. S. Edwards, An improved lower bound for the number of edges in a largest bipartite subgraph, in: M. Fiedler (ed.), Recent Advances in Graph Theory, Academia, Prague, pp. 167-181, 1975, proceedings of the Second Czechoslovak Symposium held in Prague, June 1974. [12] P. Erdos, Problems and results in graph theory and combinatorial analysis, in: J. A. Bondy and U. S. R. Murty (eds.), Graph Theory and Related Topics, Academic Press, New York, pp. 153163, 1979, proceedings of the Conference in honour of Professor W. T. Tutte on the occasion of his sixtieth birthday, held at the University of Waterloo, Waterloo, Ontario, July 5-9, 1977. [13] P. Erdos and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959), 337-356, doi:10.1007/bf02024498. [14] G. Fan, J. Hou and Q. Zeng, A bound for judicious fc-partitions of graphs, Discrete Appl. Math. 179 (2014), 86-99, doi:10.1016/j.dam.2014.07.002. [15] J. Hou and Q. Zeng, Judicious partitioning of hypergraphs with edges of size at most 2, Combin. Probab. Comput. 26 (2017), 267-284, doi:10.1017/s0963548316000274. 160 Ars Math. Contemp. 15 (2018) 147-160 [16] J. Hou and Q. Zeng, On a problem of judicious fc-partitions of graphs, J. Graph Theory 85 (2017), 619-643, doi:10.1002/jgt.22094. [17] T. R. Jensen and B. Toft, Graph Coloring Problems, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York, 1995, doi:10.1002/ 9781118032497.scard. [18] A. Kostochka, B. Sudakov and J. Verstraete, Cycles in triangle-free graphs of large chromatic number, Combinatorica 37 (2017), 481-494, doi:10.1007/s00493-015-3262-0. [19] Y. Li, C. Rousseau and W. Zang, Asymptotic upper bounds for Ramsey functions, Graphs Combin. 17 (2001), 123-128, doi:10.1007/s003730170060. [20] Y. Li and W. Zang, The independence number of graphs with a forbidden cycle and Ramsey numbers, J. Comb. Optim. 7 (2003), 353-359, doi:10.1023/b:joco.0000017383.13275.17. [21] S. C. Locke, Maximum fc-colorable subgraphs, J. Graph Theory 6 (1982), 123-132, doi:10. 1002/jgt.3190060206. [22] S. Poljak and Zs. Tuza, Bipartite subgraphs of triangle-free graphs, SIAM J. Discrete Math. 7 (1994), 307-313, doi:10.1137/s0895480191196824. [23] A. D. Scott, Judicious partitions and related problems, in: B. S. Webb (ed.), Surveys in Combinatorics 2005, Cambridge University Press, Cambridge, volume 327 of London Mathematical Society Lecture Note Series, pp. 95-117, 2005, doi:10.1017/cbo9780511734885.006, papers from the 20th British Combinatorial Conference held at the University of Durham, Durham, July 10- 15, 2005. [24] J. B. Shearer, A note on bipartite subgraphs of triangle-free graphs, Random Struct. Algor. 3 (1992), 223-226, doi:10.1002/rsa.3240030211. [25] V. K. Wei, A lower bound on the stability number of a simple graph, Technical Report 8111217-9, Bell Laboratories Technical Memorandum, Murray Hill, New Jersey, 1981. [26] B. Xu and X. Yu, Triangle-free subcubic graphs with minimum bipartite density, J. Comb. Theory Ser. B 98 (2008), 516-537, doi:10.1016/j.jctb.2007.09.001. [27] B. Xu and X. Yu, Judicious fc-partitions of graphs, J. Comb. Theory Ser. B 99 (2009), 324-337, doi:10.1016/j.jctb.2008.08.007. [28] B. Xu and X. Yu, Better bounds for fc-partitions of graphs, Combin. Probab. Comput. 20 (2011), 631-640, doi:10.1017/s0963548311000204.