Edge-coloring to avoid large monochromatic stars
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
Conjecture (proposed by Erdős, Faudree, Rousseau and Schelp [1])
In every \(3\)-coloring of the edges of \(K_n\), there is a color such that there are three vertices whose neighbors (joining by edges in such a color) include at least two-thirds of all the vertices.An example of Kierstead [1] shows the result of the conjecture is the best possible. In 2014, the conjecture was proved by Baber and Talbot [2], using flag algebras.
Bibliography | |
---|---|
1 | R. Faudree, C. C. Rousseau and R. H. Schelp, Problems in graph theory from Memphis, The Mathematics of Paul Erdős, II (R. L. Graham and J. Nešetril, eds.), 7-26, Springer-Verlag, Berlin, 1996. |
2 | R. Baber and J. Talbot, A solution to the 2/3 conjecture, SIAM J. Discrete Math, 28(2), 756-766, 2014. |