On the Folkman Number f(2, 3, 4)

Abstract

Let f(2, 3, 4) denote the smallest integer n such that there exists a K ₄-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.10⁹. 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.

Keywords:

• Primary 05C55, 05C35
• Folkman numbers
• generalized Ramsey theory
• extremal problems