A new bound for the 2/3 Conjecture

Graph Theory Seminar
Thursday, April 26, 2012 - 13:05
1 hour (actually 50 minutes)
Skiles 005
Math, GT
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. This is joint work with Daniel Kral, Chun-Hung Liu, Jean-Sebastien Sereni, and Zelealem Yilma.