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

Stanislaw P. Radziszowski

Department of Computer Science

Rochester Institute of Technology

spr@cs.rit.edu
### ABSTRACT

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.