A new bound for the 2/3 conjecture

Daniel Král', Chun Hung Liu, Jean Sébastien Sereni, Peter Whalen, Zelealem B. Yilma

Research output: Contribution to journalArticle

12 Scopus citations

Abstract

We show that any n-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 2n/3. The previous best value, proved by ErdÅ's, Faudree, Gould, Gyárfás, Rousseau and Schelp in 1989, is 22. It is conjectured that three vertices suffice.

Original languageEnglish (US)
Pages (from-to)384-393
Number of pages10
JournalCombinatorics Probability and Computing
Volume22
Issue number3
DOIs
StatePublished - May 2013

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A new bound for the 2/3 conjecture'. Together they form a unique fingerprint.

  • Cite this

    Král', D., Liu, C. H., Sereni, J. S., Whalen, P., & Yilma, Z. B. (2013). A new bound for the 2/3 conjecture. Combinatorics Probability and Computing, 22(3), 384-393. https://doi.org/10.1017/S0963548312000612