Informace o publikaci
A New Bound for the 2/3 Conjecture
| Autoři | |
|---|---|
| Rok publikování | 2013 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | COMBINATORICS PROBABILITY & COMPUTING |
| Citace | |
| Doi | http://dx.doi.org/10.1017/S0963548312000612 |
| Popis | 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. |