{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:16:18Z","timestamp":1759637778041},"reference-count":15,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T00:00:00Z","timestamp":1221177600000},"content-version":"unspecified","delay-in-days":5582,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[1993,6]]},"abstract":"<jats:p>Let G be a connected graph with <jats:italic>n<\/jats:italic> vertices and <jats:italic>m<\/jats:italic> edges (multiple edges allowed), and let <jats:italic>k<\/jats:italic> \u2265 2 be an integer. There is an algorithm with (optimal) running time of <jats:italic>O<\/jats:italic>(<jats:italic>m<\/jats:italic>) that finds<\/jats:p><jats:p>(i) a bipartite subgraph of <jats:italic>G<\/jats:italic> with \u2265 <jats:italic>m<\/jats:italic>\/2 + (<jats:italic>n<\/jats:italic> \u2212 1)\/4 edges,<\/jats:p><jats:p>(ii) a bipartite subgraph of <jats:italic>G<\/jats:italic> with \u2265 <jats:italic>m<\/jats:italic>\/2 + 3(<jats:italic>n<\/jats:italic>\u22121)\/8 edges if <jats:italic>G<\/jats:italic> is triangle-free,<\/jats:p><jats:p>(iii) a k-colourable subgraph of <jats:italic>G<\/jats:italic> with \u2265 <jats:italic>m<\/jats:italic> \u2212 <jats:italic>m<\/jats:italic>\/<jats:italic>k<\/jats:italic> + (<jats:italic>n<\/jats:italic>\u22121)\/<jats:italic>k<\/jats:italic> + (<jats:italic>k<\/jats:italic> \u2212 3)\/2 edges if <jats:italic>k<\/jats:italic> \u2265 3 and <jats:italic>G<\/jats:italic> is not k-colorable.<\/jats:p><jats:p>Infinite families of graphs show that each of those lower bounds on the worst-case performance are best possible (for every algorithm). Moreover, even if short cycles are excluded, the general lower bound of <jats:italic>m \u2212 m<\/jats:italic>\/<jats:italic>k<\/jats:italic> cannot be replaced by <jats:italic>m<\/jats:italic> \u2212 <jats:italic>m<\/jats:italic>\/<jats:italic>k<\/jats:italic> + \u03b5<jats:italic>m<\/jats:italic> for any fixed \u03b5 &gt; 0; and it is <jats:italic>NP<\/jats:italic>-complete to decide whether a graph with <jats:italic>m<\/jats:italic> edges contains a <jats:italic>k<\/jats:italic>-colorable subgraph with more than <jats:italic>m<\/jats:italic> \u2212 <jats:italic>m<\/jats:italic>\/<jats:italic>k<\/jats:italic> + \u03b5<jats:italic>m<\/jats:italic> edges, for any <jats:italic>k<\/jats:italic> \u2265 2 and \u03b5&gt; 0, \u03b5 &lt; 1\/<jats:italic>k.<\/jats:italic><\/jats:p>","DOI":"10.1017\/s0963548300000596","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T11:19:08Z","timestamp":1221218348000},"page":"201-210","source":"Crossref","is-referenced-by-count":11,"title":["Linear-Time Approximation Algorithms for the Max Cut Problem"],"prefix":"10.1017","volume":"2","author":[{"given":"Nguyen","family":"van Ngoc","sequence":"first","affiliation":[]},{"given":"Zsolt","family":"Tuza","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2008,9,12]]},"reference":[{"key":"S0963548300000596_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(92)90042-V"},{"key":"S0963548300000596_ref013","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030211"},{"key":"S0963548300000596_ref012","article-title":"Bipartite subgraphs of triangle-free graphs.","author":"Poljak","journal-title":"SIAM J. Discrete Math."},{"key":"S0963548300000596_ref008","volume-title":"Computers and Intractability \u2013 A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"S0963548300000596_ref004","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1959-003-9"},{"key":"S0963548300000596_ref002","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190150110"},{"key":"S0963548300000596_ref007","first-page":"153","volume-title":"Graph Theory and Related Topics","author":"Erd\u0151s","year":"1979"},{"key":"S0963548300000596_ref010","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1982-036-8"},{"key":"S0963548300000596_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90057-3"},{"key":"S0963548300000596_ref015","article-title":"Theorem proving through depth-first search","volume":"33","author":"Tuza","journal-title":"Acta Univ. Carolinae\u2013Math. Phys."},{"key":"S0963548300000596_ref009","unstructured":"[9] Van Ngoc Nguyen (1987) On Graph Colorings, Thesis, Hungarian Academy of Sciences, Budapest (in Hungarian)."},{"key":"S0963548300000596_ref003","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1973-048-x"},{"key":"S0963548300000596_ref011","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(86)90192-5"},{"key":"S0963548300000596_ref001","first-page":"259","article-title":"Extremal k-colourable subgraphs","volume":"16","author":"Andersen","year":"1983","journal-title":"Ars Combinatoria"},{"key":"S0963548300000596_ref005","first-page":"283","article-title":"On even subgraphs of graphs","volume":"8","author":"Erd\u0151s","year":"1964","journal-title":"Mat. Lapok"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548300000596","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T22:49:14Z","timestamp":1557960554000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548300000596\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,6]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1993,6]]}},"alternative-id":["S0963548300000596"],"URL":"https:\/\/doi.org\/10.1017\/s0963548300000596","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,6]]}}}