{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T03:41:00Z","timestamp":1777520460195,"version":"3.51.4"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,1,16]],"date-time":"2020-01-16T00:00:00Z","timestamp":1579132800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,16]],"date-time":"2020-01-16T00:00:00Z","timestamp":1579132800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00493-019-4086-0","type":"journal-article","created":{"date-parts":[[2020,1,16]],"date-time":"2020-01-16T06:02:42Z","timestamp":1579154562000},"page":"283-305","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Dense Induced Bipartite Subgraphs in Triangle-Free Graphs"],"prefix":"10.1007","volume":"40","author":[{"given":"Matthew","family":"Kwan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shoham","family":"Letzter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benny","family":"Sudakov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tuan","family":"Tran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,16]]},"reference":[{"key":"4086_CR1","doi-asserted-by":"publisher","first-page":"R12","DOI":"10.37236\/1192","volume":"1","author":"N Alon","year":"1994","unstructured":"N. Alon: Explicit Ramsey graphs and orthonormal labelings, Elec. J. Combin.1 (1994), R12.","journal-title":"Elec. J. Combin."},{"issue":"3","key":"4086_CR2","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01261315","volume":"16","author":"N Alon","year":"1996","unstructured":"N. Alon: Bipartite subgraphs, Combinatorica16 (1996), no. 3, 301\u2013311.","journal-title":"Combinatorica"},{"key":"4086_CR3","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/S0095-8956(03)00036-4","volume":"88","author":"N Alon","year":"2003","unstructured":"N. Alon, B. Bollob\u00e1s, M. Krivelevich and B. S\u00fcdakov: Maximum cuts and judicious partitions in graphs without short cycles, J. Combin. Theory Ser. B88 (2003), 329\u2013346.","journal-title":"J. Combin. Theory Ser. B"},{"key":"4086_CR4","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jctb.1999.1910","volume":"77","author":"N Alon","year":"1999","unstructured":"N. Alon, M. Krivelevich and B. Sudakov: Coloring graphs with sparse neighborhoods, J. Combin. Theory Ser. B77 (1999), 73\u201382.","journal-title":"J. Combin. Theory Ser. B"},{"key":"4086_CR5","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1017\/S0963548305007017","volume":"14","author":"N Alon","year":"2005","unstructured":"N. Alon, M. Krivelevich and B. Sudakov: MaxCut in H-free graphs, Comb. Prob. Comput.14 (2005), 629\u2013647.","journal-title":"Comb. Prob. Comput."},{"key":"4086_CR6","series-title":"Bolyai Soc. Math. Stud.","first-page":"185","volume-title":"Contemporary combinatorics","author":"B Bollob\u00e1s","year":"2002","unstructured":"B. Bollob\u00e1s and A. D. Scott: Better bounds for max cut, in: Contemporary combinatorics, 185\u2013246, Bolyai Soc. Math. Stud., 10, J\u00e1nos Bolyai Math. Soc., Budapest, 2002."},{"key":"4086_CR7","unstructured":"W. Cames van Batenburg, R. de Joannis de Verclos, R. J. Kang and F. Pirot: Bipartite induced density in triangle-free graphs, arXiv:1808.02512."},{"key":"4086_CR8","unstructured":"D. Conlon, J. Fox, M. Kwan and B. Sudakov: Hypergraph cuts above the average, Israel J. Math., to appear."},{"key":"4086_CR9","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF02760037","volume":"3","author":"P Erd\u0151s","year":"1965","unstructured":"P. Erd\u0151s: On some extremal problems in graph theory, Israel J. Math.3 (1965), 113\u2013116.","journal-title":"Israel J. Math."},{"key":"4086_CR10","unstructured":"P. Erd\u0151s: Problems and results in graph theory and combinatorial analysis, (1976), 169\u2013192. Congressus Numerantium, No. XV."},{"key":"4086_CR11","doi-asserted-by":"publisher","first-page":"475","DOI":"10.4153\/CJM-1973-048-x","volume":"3","author":"C S Edwards","year":"1973","unstructured":"C. S. Edwards: Some extremal properties of bipartite subgraphs, Canad. J. Math.3 (1973), 475\u2013485.","journal-title":"Canad. J. Math."},{"key":"4086_CR12","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0095-8956(88)90057-3","volume":"45","author":"P Erd\u0151s","year":"1988","unstructured":"P. Erd\u0151s, R. Faudree, J. Pach and J. Spencer: How to make a graph bipartite, J. Combin. Theory Ser. B45 (1988), 86\u201398.","journal-title":"J. Combin. Theory Ser. B"},{"key":"4086_CR13","series-title":"Colloq. Math. Soc. J\u00e1nos Bolyai","first-page":"239","volume-title":"Sets, graphs and numbers","author":"P Erd\u0151s","year":"1992","unstructured":"P. Erd\u0151s and M. Simonovits: How many edges should be deleted to make a triangle-free graph bipartite?, in: Sets, graphs and numbers, Colloq. Math. Soc. J\u00e1nos Bolyai 60, North-Holland, Amsterdam, 1992, 239\u2013263."},{"key":"4086_CR14","series-title":"IMA Vol. Math. Appl.","first-page":"117","volume-title":"A note on triangle-free graphs","author":"P Erd\u0151s","year":"1996","unstructured":"P. Erd\u0151s, S. Janson, T. \u0141uczak and J. Spencer: A note on triangle-free graphs, Random discrete structures (Minneapolis, MN, 1993), IMA Vol. Math. Appl., vol. 76, Springer, New York, 1996, 117\u2013119."},{"key":"4086_CR15","first-page":"377","volume-title":"Some extremal problems in graph theory","author":"P Erd\u0151s","year":"1970","unstructured":"P. Erd\u0151s and M. Simonovits: Some extremal problems in graph theory, Combinatorial theory and its applications, I (Proc. Colloq., Balatonf\u00fcred, 1969), pp. 377\u2013390, North-Holland, Amsterdam, 1970."},{"key":"4086_CR16","unstructured":"L. Esperet, R. J. Kang and S. Thomass\u00e9: Separation choosability and dense bipartite induced subgraphs, Comb. Prob. Comput., arXiv:1802.03727."},{"key":"4086_CR17","doi-asserted-by":"crossref","unstructured":"A. Frieze and M. Karo\u0144ski: Introduction to random graphs, Cambridge University Press, 2016.","DOI":"10.1017\/CBO9781316339831"},{"issue":"1\u20133","key":"4086_CR18","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/S0012-365X(00)00087-X","volume":"219","author":"J Gimbel","year":"2000","unstructured":"J. Gimbel and C. Thomassen: Coloring triangle-free graphs with fixed size, Discrete Math.219 (2000), no. 1\u20133, 275\u2013277.","journal-title":"Discrete Math."},{"key":"4086_CR19","unstructured":"H. Guo and L. Warnke: Packing nearly optimal Ramsey R(3, t) graphs, Combinatorica, accepted."},{"key":"4086_CR20","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/17M115918X","volume":"33","author":"D G Harris","year":"2019","unstructured":"D. G. Harris: Some results on chromatic number as a function of triangle count, SIAM J. Discrete Math.33 (2019), 546\u2013563.","journal-title":"SIAM J. Discrete Math."},{"key":"4086_CR21","doi-asserted-by":"publisher","first-page":"1238","DOI":"10.1137\/100819254","volume":"26","author":"T Jiang","year":"2012","unstructured":"T. Jiang and R. Seiver: Tur\u00e1n numbers of subdivided graphs, SIAM J. Discrete Math.26 (2012), 1238\u20131255.","journal-title":"SIAM J. Discrete Math."},{"key":"4086_CR22","unstructured":"A. Johansson: Asymptotic choice number for triangle-free graphs, Technical Report 91-5, DIMACS, 1996."},{"key":"4086_CR23","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1002\/rsa.3240070204","volume":"7","author":"M Krivelevich","year":"1995","unstructured":"M. Krivelevich: Bounding Ramsey numbers through large deviation inequalities, Random Struct. Algor.7 (1995), 145\u2013155.","journal-title":"Random Struct. Algor."},{"key":"4086_CR24","first-page":"199","volume-title":"Pseudo-random graphs","author":"M Krivelevich","year":"2006","unstructured":"M. Krivelevich and B. Sudakov: Pseudo-random graphs, in More sets, graphs and numbers, 199\u2013262, Springer, Berlin, Heidelberg, 2006."},{"key":"4086_CR25","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1016\/j.jctb.2018.06.007","volume":"134","author":"M Molloy","year":"2019","unstructured":"M. Molloy: The list chromatic number of graphs with small clique number, J. Combin. Theory Ser. B134 (2019), 264\u2013184.","journal-title":"J. Combin. Theory Ser. B"},{"key":"4086_CR26","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0012-365X(99)00109-0","volume":"211","author":"A Nilli","year":"2000","unstructured":"A. Nilli: Triangle-free graphs with large chromatic numbers, Discrete Math.211 (2000), 261\u2013262.","journal-title":"Discrete Math."},{"key":"4086_CR27","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1137\/S0895480191196824","volume":"7","author":"S Poljak","year":"1994","unstructured":"S. Poljak and Z. Tuza: Bipartite subgraphs of triangle-free graphs, SIAM J. Discrete Math.7 (1994), 307\u2013313.","journal-title":"SIAM J. Discrete Math."},{"key":"4086_CR28","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/s00493-007-2238-0","volume":"27","author":"B Sudakov","year":"2007","unstructured":"B. Sudakov: Making a K4-free graph bipartite, Combinatorica27 (2007), 509\u2013518.","journal-title":"Combinatorica"},{"key":"4086_CR29","first-page":"436","volume":"48","author":"P Tur\u00e1n","year":"1941","unstructured":"P. Tur\u00e1n: On an external problem in graph theory, Mat. Fiz. Lapok48 (1941), 436\u2013452.","journal-title":"Mat. Fiz. Lapok"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-019-4086-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-019-4086-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-019-4086-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,15]],"date-time":"2021-01-15T00:10:34Z","timestamp":1610669434000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-019-4086-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,16]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["4086"],"URL":"https:\/\/doi.org\/10.1007\/s00493-019-4086-0","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,16]]},"assertion":[{"value":"29 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}