A New Bound for the 2/3 Conjecture Academic Article uri icon

abstract

  • We show that anyn-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 Erds, Faudree, Gould, Gyrfs, Rousseau and Schelp in 1989, is 22. It is conjectured that three vertices suffice.

published proceedings

  • Combinatorics Probability Computing

author list (cited authors)

  • KRL', D., LIU, C., SERENI, J., WHALEN, P., & YILMA, Z. B.

citation count

  • 14

complete list of authors

  • KRÁL', DANIEL||LIU, CHUN-HUNG||SERENI, JEAN-SÉBASTIEN||WHALEN, PETER||YILMA, ZELEALEM B

publication date

  • May 2013