Computing the Folkman Number $F_v(2,2,3;4)$

Abstract

We discuss a branch of Ramsey theory concerning vertex Folkman numbers and how computer algorithms have been used to compute a new Folkman number. We write $G\to (a_1,\dots ,a_k{)}^v$ if for every vertex $k$-coloring of an undirected simple graph $G$, a monochromatic $K_{a_i}$ is forced in color $i\in \{1,\dots ,k\}$. The vertex Folkman number is defined as

$$F_v(a_1,\dots ,a_k;p)=\text{min}\{|V(G)|:G\to (a_1,\dots ,a_k{)}^v\wedge K_p⊈G\}.$$

Folkman showed in 1970 that this number exists for $p>\text{max}\{a_1,\dots ,a_k\}$. Let $m=1+\sum _{i=1}^k(a_i–1)$ and $a=\text{max}\{a_1,\dots ,a_k\}$, then

$$F_v(a_1,\dots ,a_k;p)=m\text{ for }p>m,$$

and

$$F_v(a_1,\dots ,a_k;p)=a+m\text{ for }p=m.$$

For $p<m$ the situation is more difficult and much less is known. We show here that, for a case of $p=m–1$, $F_v(2,2,3;4)=14$.