{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,29]],"date-time":"2024-08-29T09:01:55Z","timestamp":1724922115016},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,5,26]],"date-time":"2011-05-26T00:00:00Z","timestamp":1306368000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2012,7]]},"DOI":"10.1007\/s00373-011-1056-8","type":"journal-article","created":{"date-parts":[[2011,5,25]],"date-time":"2011-05-25T09:34:54Z","timestamp":1306316094000},"page":"563-574","source":"Crossref","is-referenced-by-count":3,"title":["Maximum Directed Cuts in Graphs with Degree Constraints"],"prefix":"10.1007","volume":"28","author":[{"given":"Baogang","family":"Xu","sequence":"first","affiliation":[]},{"given":"Xingxing","family":"Yu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,5,26]]},"reference":[{"key":"1056_CR1","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/BF01261315","volume":"16","author":"N. Alon","year":"1996","unstructured":"Alon N.: Bipartite subgraphs. Combinatorica 16, 301\u2013311 (1996)","journal-title":"Combinatorica"},{"key":"1056_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/jgt.20215","volume":"55","author":"N. Alon","year":"2007","unstructured":"Alon N., Bollob\u00e1s B., Gy\u00e1rf\u00e1s A., Lehel J., Scott A.: Maximum dicuts in acyclic digraphs. J. Graph Theory 55, 1\u201313 (2007)","journal-title":"J. Graph Theory"},{"key":"1056_CR3","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: On some tighter inapproximability results. (extended abstract.) In: Lecture Notes in Computer Science, vol. 1644, pp. 200\u2013209. Springer, Berlin (1999)","DOI":"10.1007\/3-540-48523-6_17"},{"key":"1056_CR4","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1002\/jgt.3190100407","volume":"10","author":"J.A. Bondy","year":"1986","unstructured":"Bondy J.A., Locke S.C.: Largest bipartite subgraphs in triangle-free graphs with maximum degree three. J. Graph Theory 10, 477\u2013504 (1986)","journal-title":"J. Graph Theory"},{"key":"1056_CR5","doi-asserted-by":"crossref","first-page":"1988","DOI":"10.1016\/j.disc.2005.09.020","volume":"306","author":"M. Cropper","year":"2006","unstructured":"Cropper M., Gy\u00e1rf\u00e1s A., Lehel J.: Hall ratio of the Mycielski graphs. Discrete Math. 306, 1988\u20131990 (2006)","journal-title":"Discrete Math."},{"key":"1056_CR6","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0012-365X(01)00117-0","volume":"241","author":"A. Daneshgar","year":"2001","unstructured":"Daneshgar A., Hilton A.J.W., Johnson P.D. Jr: Relations among the fractional chromatic, choice, Hall, and Hall-condition numbers of simple graphs. Discrete Math. 241, 189\u2013199 (2001)","journal-title":"Discrete Math."},{"key":"1056_CR7","doi-asserted-by":"crossref","first-page":"475","DOI":"10.4153\/CJM-1973-048-x","volume":"25","author":"C.S. Edwards","year":"1973","unstructured":"Edwards C.S.: Some extremal properties of bipartite graphs. Can. J. Math. 25, 475\u2013485 (1973)","journal-title":"Can. J. Math."},{"key":"1056_CR8","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/S0196-6774(02)00005-6","volume":"43","author":"U. Feige","year":"2002","unstructured":"Feige U., Karpinski M., Langberg M.: Improved approximation of max-cut on graphs of bounded degree. J. Algorithms 43, 201\u2013219 (2002)","journal-title":"J. Algorithms"},{"key":"1056_CR9","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans M.X., Williamson D.P.: Improved approximation algorithms for maximum cut and satisfiability using semidefinite programming. J. ACM 42, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"1056_CR10","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/j.jalgor.2004.06.001","volume":"53","author":"E. Halperin","year":"2004","unstructured":"Halperin E., Livnant D., Zwick U.: MAX CUT in cubic graphs. J. Algorithm 53, 169\u2013185 (2004)","journal-title":"J. Algorithm"},{"key":"1056_CR11","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1002\/jgt.3190060205","volume":"6","author":"G. Hopkins","year":"1982","unstructured":"Hopkins G., Staton W.: Extremal bipartite subgraphs of cubic triangle-free graphs. J. Graph Theory 6, 115\u2013121 (1982)","journal-title":"J. Graph Theory"},{"key":"1056_CR12","first-page":"183","volume":"37","author":"P.D. Johnson Jr","year":"1994","unstructured":"Johnson P.D. Jr: The Hall condition number of a graph. Ars Combinatoria 37, 183\u2013190 (1994)","journal-title":"Ars Combinatoria"},{"key":"1056_CR13","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"1056_CR14","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1002\/jgt.20374","volume":"61","author":"J. Lehel","year":"2009","unstructured":"Lehel J., Maffray F., Preissmann M.: Maximum directed cuts in digraphs with degree restriction. J. Graph Theory 61, 140\u2013156 (2009)","journal-title":"J. Graph Theory"},{"key":"1056_CR15","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1002\/jgt.3190060206","volume":"6","author":"S.C. Locke","year":"1982","unstructured":"Locke S.C.: Maximum k-colourable subgraphs. J. Graph Theory 6, 123\u2013132 (1982)","journal-title":"J. Graph Theory"},{"key":"1056_CR16","first-page":"103","volume":"10","author":"W. Staton","year":"1980","unstructured":"Staton W.: Edge deletions and the chromatic number. Ars Combinatoria 10, 103\u2013106 (1980)","journal-title":"Ars Combinatoria"},{"key":"1056_CR17","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1016\/j.jctb.2007.09.001","volume":"98","author":"B. Xu","year":"2008","unstructured":"Xu B., Yu X.: Triangle-free subcubic graphs with minimum bipartite density. J. Combin. Theory Ser. B 98, 516\u2013537 (2008)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1056_CR18","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Node- and edge-deletion NP-complete problems. In: STOC, pp. 253\u2013264 (1978)","DOI":"10.1145\/800133.804355"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-011-1056-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-011-1056-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-011-1056-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T04:45:42Z","timestamp":1560228342000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-011-1056-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,26]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["1056"],"URL":"https:\/\/doi.org\/10.1007\/s00373-011-1056-8","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5,26]]}}}