### 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

## 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