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

Abstract

For a graph $G$, the expression $G\stackrel{v}{\to }(a_1,\dots ,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,\dots ,r\}$. The vertex Folkman numbers are defined as $F_v(a_1,\dots ,a_r;q)=\text{min}\{|V(G)|:G\stackrel{v}{\to }(a_1,\dots ,a_r)\text{ and }{K}_q⊈G\}$. Of these, the only Folkman number of the form $F(\underbrace{2,\dots ,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)\le 16$ are the two Ramsey $(4,4)$-graphs on $16$ vertices.