{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T07:11:31Z","timestamp":1772521891666,"version":"3.50.1"},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2017,9,28]],"date-time":"2017-09-28T00:00:00Z","timestamp":1506556800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Bollob\u00e1s and Scott (<jats:italic>Random Struct. Alg.<\/jats:italic><jats:bold>21<\/jats:bold>(2002) 414\u2013430) asked for conditions that guarantee a bisection of a graph with<jats:italic>m<\/jats:italic>edges in which each class has at most (1\/4+<jats:italic>o<\/jats:italic>(1))<jats:italic>m<\/jats:italic>edges. We demonstrate that cycles of length 4 play an important role for this question. Let<jats:italic>G<\/jats:italic>be a graph with<jats:italic>m<\/jats:italic>edges, minimum degree \u03b4, and containing no cycle of length 4. We show that if (i)<jats:italic>G<\/jats:italic>is 2-connected, or (ii) \u03b4 \u2a7e 3, or (iii) \u03b4 \u2a7e 2 and the girth of<jats:italic>G<\/jats:italic>is at least 5, then<jats:italic>G<\/jats:italic>admits a bisection in which each class has at most (1\/4+<jats:italic>o<\/jats:italic>(1))<jats:italic>m<\/jats:italic>edges. We show that each of these conditions are best possible. On the other hand, a construction by Alon, Bollob\u00e1s, Krivelevich and Sudakov shows that for infinitely many<jats:italic>m<\/jats:italic>there exists a graph with<jats:italic>m<\/jats:italic>edges and girth at least 5 for which any bisection has at least (1\/4\u2212<jats:italic>o<\/jats:italic>(1))<jats:italic>m<\/jats:italic>edges in one of the two classes.<\/jats:p>","DOI":"10.1017\/s0963548317000487","type":"journal-article","created":{"date-parts":[[2017,9,28]],"date-time":"2017-09-28T09:42:14Z","timestamp":1506591734000},"page":"44-59","source":"Crossref","is-referenced-by-count":22,"title":["Bisections of Graphs Without Short Cycles"],"prefix":"10.1017","volume":"27","author":[{"given":"GENGHUA","family":"FAN","sequence":"first","affiliation":[]},{"given":"JIANFENG","family":"HOU","sequence":"additional","affiliation":[]},{"given":"XINGXING","family":"YU","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2017,9,28]]},"reference":[{"key":"S0963548317000487_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.09.001"},{"key":"S0963548317000487_ref19","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1002\/jgt.20421","article-title":"Balanced judicious partitions of graphs","volume":"63","author":"Xu","year":"2010","journal-title":"J. Graph Theory"},{"key":"S0963548317000487_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)00004-6"},{"key":"S0963548317000487_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.07.007"},{"key":"S0963548317000487_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.01.004"},{"key":"S0963548317000487_ref23","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000204"},{"key":"S0963548317000487_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2010.03.029"},{"key":"S0963548317000487_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.06.002"},{"key":"S0963548317000487_ref6","first-page":"185","volume-title":"Contemporary Combinatorics","author":"Bollob\u00e1s","year":"2002"},{"key":"S0963548317000487_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01261315"},{"key":"S0963548317000487_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20642"},{"key":"S0963548317000487_ref3","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1996.2744"},{"key":"S0963548317000487_ref18","first-page":"95","volume-title":"Surveys in Combinatorics","author":"Scott","year":"2005"},{"key":"S0963548317000487_ref9","unstructured":"Edwards C. S. (1975) An improved lower bound for the number of edges in a largest bipartite subgraph. In Proc. 2nd Czechoslovak Symposium on Graph Theory, pp. 167\u2013181."},{"key":"S0963548317000487_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00036-4"},{"key":"S0963548317000487_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90052-5"},{"key":"S0963548317000487_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10062"},{"key":"S0963548317000487_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-015-1529-2"},{"key":"S0963548317000487_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-015-2944-y"},{"key":"S0963548317000487_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548316000274"},{"key":"S0963548317000487_ref8","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1973-048-x"},{"key":"S0963548317000487_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.08.007"},{"key":"S0963548317000487_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2010.06.002"},{"key":"S0963548317000487_ref17","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480191196824"},{"key":"S0963548317000487_ref4","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1007\/s004939970002","article-title":"Exact bounds for judicious partitions of graphs","volume":"19","author":"Bollob\u00e1s","year":"1999","journal-title":"Combinatorica"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548317000487","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,27]],"date-time":"2024-06-27T09:40:08Z","timestamp":1719481208000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548317000487\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,28]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["S0963548317000487"],"URL":"https:\/\/doi.org\/10.1017\/s0963548317000487","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,28]]}}}