Computing the Folkman Number \(F_{v}(2, 2, 2, 2, 2; 4)\)

For a graph \( G \), the expression \( G \overset{v}{\rightarrow} (a_1, \ldots, a_r) \) means that for any \( r \)-coloring of the vertices of \( G \) there exists a monochromatic \( a_i \)-clique in \( G \) for some color \( i \in \{1, \ldots, r\} \). The vertex Folkman numbers are defined as \( F_v(a_1, \ldots, a_r; q) = \text{min}\{|V(G)| : G \overset{v}{\rightarrow} (a_1, \ldots, a_r) \text{ and } K_q \not\subseteq G\} \). Of these, the only Folkman number of the form \( F(\underbrace{2, \ldots, 2}; r – 1) \) which has remained unknown up to this time is \( F_v(2, 2, 2, 2, 2; 4) \).

We show here that \( F_v(2, 2, 2, 2, 2; 4) = 16 \), which is equivalent to saying that the smallest \( 6 \)-chromatic \( K_4 \)-free graph has \( 16 \) vertices. We also show that the sole witnesses of the upper bound \( F_v(2, 2, 2, 2, 2; 4) \leq 16 \) are the two Ramsey \( (4, 4) \)-graphs on \( 16 \) vertices.