Skip to Main content Skip to Navigation
Reports

A new bound for the 2/3 conjecture

Abstract : 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 et al. in 1989, is 22. It is conjectured that three vertices suffice.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-00686989
Contributor : Jean-Sébastien Sereni <>
Submitted on : Wednesday, April 11, 2012 - 6:16:43 PM
Last modification on : Thursday, March 26, 2020 - 9:17:48 PM
Long-term archiving on: : Thursday, July 12, 2012 - 10:00:48 AM

Files

twothirds.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00686989, version 1
  • ARXIV : 1204.2519

Collections

Citation

Daniel Král', Chun-Hung Liu, Jean-Sébastien Sereni, Peter Whalen, Zelealem Yilma. A new bound for the 2/3 conjecture. 2012. ⟨hal-00686989v1⟩

Share

Metrics

Record views

116

Files downloads

29