A new bound for the 2/3 conjecture

We show that any n-vertex complete graph with edges colored with three colors contains a set of at most four vertices such that the number of the neighbors of these vertices in one of the colors is at least 2n/3. The previous best value, proved by Erdos, Faudree, Gould, Gyárfás, Rousseau and Schelp in 1989, is 22. It is conjectured that three vertices suffice.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00686989
Author Král', Daniel, Liu, Chun-Hung, Sereni, Jean-Sébastien, Whalen, Peter, Yilma, Zelealem
Maintainer CCSD
Last Updated May 28, 2026, 23:53 (UTC)
Created May 28, 2026, 23:53 (UTC)
Identifier hal-00686989
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Centre for Discrete Mathematics and its Applications [Warwick] (DIMAP) ; University of Warwick [Coventry]
creator Král', Daniel
date 2012-05-28T00:00:00
harvest_object_id 30484058-bc69-484a-ae51-8abec9857322
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-11-04T00:00:00
relation info:eu-repo/semantics/altIdentifier/arxiv/1204.2519
set_spec type:REPORT