{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:19:19Z","timestamp":1758824359536},"reference-count":27,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2013,1,23]],"date-time":"2013-01-23T00:00:00Z","timestamp":1358899200000},"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":[[2013,5]]},"abstract":"<jats:p>We show that any<jats:italic>n<\/jats:italic>-vertex complete graph with edges coloured with three colours contains a set of at most four vertices such that the number of the neighbours of these vertices in one of the colours is at least 2<jats:italic>n<\/jats:italic>\/3. The previous best value, proved by Erd\u0151s, Faudree, Gould, Gy\u00e1rf\u00e1s, Rousseau and Schelp in 1989, is 22. It is conjectured that three vertices suffice.<\/jats:p>","DOI":"10.1017\/s0963548312000612","type":"journal-article","created":{"date-parts":[[2013,1,23]],"date-time":"2013-01-23T12:13:03Z","timestamp":1358943183000},"page":"384-393","source":"Crossref","is-referenced-by-count":15,"title":["A New Bound for the 2\/3 Conjecture"],"prefix":"10.1017","volume":"22","author":[{"given":"DANIEL","family":"KR\u00c1L'","sequence":"first","affiliation":[]},{"given":"CHUN-HUNG","family":"LIU","sequence":"additional","affiliation":[]},{"given":"JEAN-S\u00c9BASTIEN","family":"SERENI","sequence":"additional","affiliation":[]},{"given":"PETER","family":"WHALEN","sequence":"additional","affiliation":[]},{"given":"ZELEALEM B.","family":"YILMA","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2013,1,23]]},"reference":[{"key":"S0963548312000612_ref8","first-page":"29","article-title":"Monochromatic coverings in colored complete graphs. In","volume":"71","author":"Erd\u0151s","year":"1990","journal-title":"Proc. Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing. Congr. Numer."},{"key":"S0963548312000612_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.07.008"},{"key":"S0963548312000612_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130607"},{"key":"S0963548312000612_ref6","unstructured":"Cummings J. , Kr\u00e1l' D. , Pfender F. , Sperfeld K. , Treglown A. and Young M. Monochromatic triangles in three-coloured graphs. Submitted. arXiv:1206.1987."},{"key":"S0963548312000612_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/BF01782364"},{"key":"S0963548312000612_ref3","doi-asserted-by":"crossref","DOI":"10.37236\/2360","article-title":"New Tur\u00e1n densities for 3-graphs","volume":"19","author":"Baber","year":"2012","journal-title":"Electron. J. Combin."},{"key":"S0963548312000612_ref14","unstructured":"Hatami H. , Hladk\u00fd J. , Kr\u00e1l' D. , Norine S. and Razborov A. On the number of pentagons in triangle-free graphs. J. Combin. Theory Ser. A. Submitted. arXiv:1102.1634."},{"key":"S0963548312000612_ref16","unstructured":"Hirst J. The inducibility of graphs on four vertices. Submitted. arXiv:1109.1592."},{"key":"S0963548312000612_ref13","unstructured":"Hatami H. , Hirst J. and Norine S. The inducibility of blow-up graphs. Submitted. arXiv:1108.5699."},{"key":"S0963548312000612_ref20","unstructured":"Kramer L. , Martin R. R. and Young M. On diamond-free subposets of the Boolean lattice. J. Combin. Theory Ser. A. Submitted. arXiv:1205.1501."},{"key":"S0963548312000612_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.04.001"},{"key":"S0963548312000612_ref10","unstructured":"Falgas-Ravry V. and Vaughan E. R. On applications of Razborov's flag algebra calculus to extremal 3-graph theory. Submitted. arXiv:1110.1623."},{"key":"S0963548312000612_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90045-0"},{"key":"S0963548312000612_ref11","unstructured":"Falgas-Ravry V. and Vaughan E. R. Tur\u00e1n H-densities for 3-graphs. Submitted. arXiv:1201.4326."},{"key":"S0963548312000612_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000107"},{"key":"S0963548312000612_ref22","unstructured":"Pikhurko O. Minimum number of k-cliques in graphs with bounded independence number. Submitted. arXiv:1203.4393."},{"key":"S0963548312000612_ref17","unstructured":"Hladk\u00fd J. , Kr\u00e1l' D. and Norine S. Counting flags in triangle-free digraphs. Submitted. arXiv:0908.2791."},{"key":"S0963548312000612_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9419-3"},{"key":"S0963548312000612_ref26","doi-asserted-by":"publisher","DOI":"10.1137\/090747476"},{"key":"S0963548312000612_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.05.002"},{"key":"S0963548312000612_ref23","unstructured":"Pikhurko O. and Razborov, A. Asymptotic structure of graphs with the minimum number of triangles. Submitted. arXiv:1204.2846."},{"key":"S0963548312000612_ref24","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1203350785"},{"key":"S0963548312000612_ref18","unstructured":"Kr\u00e1l' D. , Liu C.-H. , Sereni J.-S. , Whalen P. and Yilma Z. B. A new bound for the 2\/3 conjecture. arXiv:1204.2519."},{"key":"S0963548312000612_ref25","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009085"},{"key":"S0963548312000612_ref1","unstructured":"Baber R. Tur\u00e1n densities of hypercubes. Submitted. arXiv:1201.3587."},{"key":"S0963548312000612_ref4","unstructured":"Balogh J. , Hu P. , Lidick\u00fd B. and Liu H. Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube. Submitted. arXiv:1201.0209."},{"key":"S0963548312000612_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548310000222"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548312000612","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,21]],"date-time":"2020-07-21T02:41:20Z","timestamp":1595299280000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548312000612\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,23]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["S0963548312000612"],"URL":"https:\/\/doi.org\/10.1017\/s0963548312000612","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1,23]]}}}