Publication details
A New Bound for the 2/3 Conjecture
| Authors | |
|---|---|
| Year of publication | 2013 |
| Type | Article in Periodical |
| Magazine / Source | COMBINATORICS PROBABILITY & COMPUTING |
| Citation | |
| Doi | http://dx.doi.org/10.1017/S0963548312000612 |
| Description | 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 Erdos, Faudree, Gould, Gyarfas, Rousseau and Schelp in 1989, is 22. It is conjectured that three vertices suffice. |