The vertex Folkman Numbers $F_v(a_1,\dots ,a_s;m-1)=m+9,$ if $max\{a_1,\dots ,a_s\}=5$

Abstract

For a graph $G$, the expression $G\stackrel{v}{\to }(a_1,\dots ,a_s)$ means that for any $s$-coloring of the vertices of $G$, there exists $i\in \{1,\dots ,s\}$ such that there is a monochromatic $a_i$-clique of color $i$. The vertex Folkman numbers

$$F_v(a_1,\dots ,a_s;m-1)=min\{|V(G)|:G\stackrel{v}{\to }(a_1,\dots ,a_s)\text{ and }{K}_{m-1}⊈G\}$$

are considered, where $m=\sum _{i=1}^s(a_i–1)+1$.

With the help of a computer, we show that $F_v(2,2,5;6)=16$, and then we prove

$$F_v(a_1,\dots ,a_s;m-1)=m+9,$$

if $max\{a_1,\dots ,a_s\}=5$.

We also obtain the bounds

$$m+9\le F_v(a_1,\dots ,a_s;m-1)\le m+10,$$

if $max\{a_1,\dots ,a_s\}=6$.