On the vertex Folkman numbers $F_v(a_1,..,a_s;m–1)$ when $max{a}_1,\dots ,a_s$ = 6 or 7

Abstract

Let G be a graph and a1,…, as be positive integers. The expression $G\underrightarrow{v}(a_1,\dots ,a_s)$ means that for every coloring of the vertices of G in s colors 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;q)$ are defined by the equality:
$$F_v(a_1,\dots ,a_s;q)=min\{|V(G)|:G\underrightarrow{v}(a_1,\dots ,a_s)and{K}_q⊈G\}$$.
Let $m=\sum _{i=1}^s(a_i–1)+1$. It is easy to see that $F_v(a_1,\dots ,a_s;q)=m$ if $q\ge m+1$. In [11] it is proved that $F_v(a_1,\dots ,a_s;m)=m+max{a}_1,\dots ,a_s$. We know all the numbers $F_v(a_1,\dots ,a_s;m–1)$ when $max{a}_1,..,a_s\le 5$ and none of these numbers is known if $max{a}_1,\dots ,a_s\ge 6$. In this paper we present computer algorithms, with the help of which we compute all Folkman numbers $F_v(a_1,..,a_s;m–1)$ when $max{a}_1,..,a_s=6$. We also prove that $F_v(2,2,7;8)=20$ and obtain new bounds on the numbers $F_v(a_1,\dots ,a_s;m–1)$ when $max(a_1,\dots ,a_s)=7$.