{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T16:24:32Z","timestamp":1776270272847,"version":"3.50.1"},"reference-count":8,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2011,5,31]],"date-time":"2011-05-31T00:00:00Z","timestamp":1306800000000},"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":[[2011,7]]},"abstract":"<jats:p>Let <jats:italic>G<\/jats:italic> be a graph with <jats:italic>m<\/jats:italic> edges, and let <jats:italic>k<\/jats:italic> be a positive integer. We show that <jats:italic>V<\/jats:italic>(<jats:italic>G<\/jats:italic>) admits a <jats:italic>k<\/jats:italic>-partition <jats:italic>V<\/jats:italic><jats:sub>1<\/jats:sub>, .\u00a0.\u00a0. <jats:italic>V<\/jats:italic><jats:sub><jats:italic>k<\/jats:italic><\/jats:sub> such that <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000204_inline1\"><jats:alt-text>$e(V_i)\\leq \\frac 1{k^2}m+\\frac {k-1}{2k^2}(\\sqrt{2m+1\/4}-1\/2)$<\/jats:alt-text><\/jats:inline-graphic> for <jats:italic>i<\/jats:italic> \u2208 {1, 2, .\u00a0.\u00a0. <jats:italic>k<\/jats:italic>}, and <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000204_inline2\"><jats:alt-text>$e(V_1, \\ldots, V_k)\\geq \\frac{k-1}{ k} m +\\frac{k-1}{ 2k}\\sqrt{2m+1\/4} +O(k)$<\/jats:alt-text><\/jats:inline-graphic>, where <jats:italic>e<\/jats:italic>(<jats:italic>V<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub>) denotes the number of edges with both ends in <jats:italic>V<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub> and <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000204_inline3\"><jats:alt-text>$e(V_1,\\ldots, V_k)=m-\\sum_{i=1}^ke(V_i)$<\/jats:alt-text><\/jats:inline-graphic>. This answers a problem of Bollob\u00e1s and Scott [2] in the affirmative. Moreover, <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000204_inline4\"><jats:alt-text>$\\binom{k+1}{ 2}e(V_i)+\\frac k2\\sum_{j\\ne i}e(V_j)\\le m + O(k^2)$<\/jats:alt-text><\/jats:inline-graphic> for <jats:italic>i<\/jats:italic> \u2208 {1, 2, .\u00a0.\u00a0., <jats:italic>k<\/jats:italic>}, which is close to being best possible and settles another problem of Bollob\u00e1s and Scott [2].<\/jats:p>","DOI":"10.1017\/s0963548311000204","type":"journal-article","created":{"date-parts":[[2011,5,31]],"date-time":"2011-05-31T13:19:47Z","timestamp":1306847987000},"page":"631-640","source":"Crossref","is-referenced-by-count":25,"title":["Better Bounds for <i>k<\/i>-Partitions of Graphs"],"prefix":"10.1017","volume":"20","author":[{"given":"BAOGANG","family":"XU","sequence":"first","affiliation":[]},{"given":"XINGXING","family":"YU","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2011,5,31]]},"reference":[{"key":"S0963548311000204_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.08.007"},{"key":"S0963548311000204_ref5","unstructured":"[5] 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":"S0963548311000204_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10062"},{"key":"S0963548311000204_ref1","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"},{"key":"S0963548311000204_ref6","first-page":"95","volume-title":"Surveys in Combinatorics","author":"Scott","year":"2005"},{"key":"S0963548311000204_ref4","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1973-048-x"},{"key":"S0963548311000204_ref7","first-page":"111","article-title":"Graph partitions.","volume":"15","author":"Porter","year":"1994","journal-title":"J. Combin. Math. Combin. Comp."},{"key":"S0963548311000204_ref3","first-page":"185","volume-title":"Contemporary Combinatorics","author":"Bollob\u00e1s","year":"2002"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548311000204","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T07:57:26Z","timestamp":1556351846000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548311000204\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,31]]},"references-count":8,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["S0963548311000204"],"URL":"https:\/\/doi.org\/10.1017\/s0963548311000204","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5,31]]}}}