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 language | English (US) |
---|---|
Pages (from-to) | 384-393 |
Number of pages | 10 |
Journal | Combinatorics Probability and Computing |
Volume | 22 |
Issue number | 3 |
DOIs | |
State | Published - May 2013 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics