On the Folkman Number ${f(2,3,4)}$
Dudek, Andrzej ; Rödl, Vojtĕech
Experiment. Math., Tome 17 (2008) no. 1, p. 63-67 / Harvested from Project Euclid
Let $f(2,3,4)$} denote the smallest integer $n$ such that there exists a l$K_4$}-free graph of order $n$ for which any $2$-coloring of its edges yields at least one monochromatic triangle. It is well known that such a number must exist. For a long time, the best known upper bound, provided by J. Spencer, was $f(2,3,4)$ < 3 \cdot 10^9. Recently, L. Lu announced that $f(2,3,4)$ < 10,000. In this note, we will give a computer-assisted proof showing that $f(2,3,4)$ < 1000. To prove this, we will generalize an idea of Goodman's, giving a necessary and sufficient condition for a graph $G$ to yield a monochromatic triangle for every edge coloring.
Publié le : 2008-05-15
Classification:  Folkman numbers,  generalized Ramsey theory,  extremal problems,  05C55,  05C35
@article{1227031897,
     author = {Dudek, Andrzej and R\"odl, Vojt\u eech},
     title = {On the Folkman Number ${f(2,3,4)}$},
     journal = {Experiment. Math.},
     volume = {17},
     number = {1},
     year = {2008},
     pages = { 63-67},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1227031897}
}
Dudek, Andrzej; Rödl, Vojtĕech. On the Folkman Number ${f(2,3,4)}$. Experiment. Math., Tome 17 (2008) no. 1, pp.  63-67. http://gdmltest.u-ga.fr/item/1227031897/