%T A solution to the 2/3 conjecture
%V 28
%A JM Talbot
%A R Baber
%N 2
%P 756-766
%D 2014
%I Society for Industrial and Applied Mathematics
%J SIAM Journal on Discrete Mathematics
%K Vertex domination, Ramsey theory
%L discovery1529895
%X We prove a vertex domination conjecture of Erd˝os, Faudree, Gould, Gy´arf´as,
Rousseau, and Schelp that for every n-vertex complete graph with edges colored using three colors
there exists a set of at most three vertices which have at least 2n/3 neighbors in one of the colors.
Our proof makes extensive use of the ideas presented in [D. Kr´al’ et al., A new bound for the 2/3
conjecture, Combin. Probab. Comput. 22 (2013), pp. 384–393].
%O This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions.