A new bound for the 2/3 conjecture
arXiv:1204.2519
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, Faudree, Gould, Gyárfás, Rousseau and Schelp in 1989, is 22. It is conjectured that three vertices suffice.
References in corpus (7)
- On the Number of Pentagons in Triangle-Free Graphs
- Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
- Asymptotic Structure of Graphs with the Minimum Number of Triangles
- On diamond-free subposets of the Boolean lattice
- Turán densities of hypercubes
- Minimum Number of k-Cliques in Graphs with Bounded Independence Number
- The inducibility of blow-up graphs