New Folkman Number F(3,3;5)=15

Stanislaw P. Radziszowski
Department of Computer Science
Rochester Institute of Technology


With the help of computer algorithms we prove that 15 is the exact value of the (edge) Folkman number F_e (3,3;5), which is defined as the smallest positive integer n, such that there exists a K_5-free graph on n vertices, whose every coloring of the edges with two colors contains a monochromatic triangle. We construct all critical graphs on 15 vertices for this number and present some of their properties. Similarly, we obtain F_v (3,3;4) = 14 and all K_4-free critical graphs for the (vertex) Folkman number, where instead of the edges we color the vertices. The exact values of both numbers were previously unknown, and both were the smallest open cases of a general problem of computing edge- and vertex- Folkman numbers F(k,l;m), respectively.

The above results are described in detail in a joint paper with Konrad Piwakowski and Sebastian Urbanski.

A bizarre open case of F_e(3,3;4) is suggested for consideration.

Colloquia Series page.