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

Abstract

Let $G$ be a graph and $a_1,...,a_s$ be positive integers. Then $G\stackrel{v}{\to }(a_1,...,a_s)$ means that for every coloring of the vertices of $G$ in $s$ colors there exists $i\in \{1,...,s\}$, such that there is a monochromatic $a_i$-clique of color $i$. The vertex Folkman number $F_v(a_1,...,a_s;q)$ is defined by the equality: $$ F_v(a_1, ..., a_s; q) = \min\{|V(G)| : G \overset{v}{\rightarrow} (a_1, ..., a_s) \mbox{ and } K_q \not\subseteq G\}. $$ Let $m=\sum _{i=1}^s(a_i-1)+1$. It is easy to see that $F_v(a_1,...,a_s;q)=m$ if $q\ge m+1$. In [11] it is proved that $F_v(a_1,...,a_s;m)=m+\max \{a_1,...,a_s\}$. We know all the numbers $F_v(a_1,...,a_s;m-1)$ when $\max \{a_1,...,a_s\}\le 5$ and none of these numbers is known if $\max \{a_1,...,a_s\}\ge 6$. In this paper we compute the numbers $F_v(a_1,...,a_s;m-1)$ when $\max \{a_1,...,a_s\}=6$.

arXiv commentIn the current version we use new faster algorithms with the help of which we reproduce the results from the previous version and we also prove new theorems (Theorem 1.5, Theorem 1.6, Theorem 1.7, Theorem 1.8)