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

Abstract

For a graph $G$ the expression $G\stackrel{v}{\to }(a_1,...,a_s)$ means that for any $s$-coloring of the vertices of $G$ there exists $i\in \{1,...,s\}$ such that there is a monochromatic $a_i$-clique of color $i$. The vertex Folkman numbers $$F_v(a_1, ..., a_s; m - 1) = \min\{\vert V(G) \vert : G \overset{v}{\rightarrow} (a_1, ..., a_s) \mbox{ and } K_{m - 1} \not\subseteq G\}.$$ are considered, where $m={\sum }_{i=1}^s(a_i-1)+1$. With the help of computer we show that $F_v(2,2,5;6)=16$ and then we prove $$F_v(a_1,...,a_s;m-1)=m+9,$$ if $\max \{a_1,...,a_s\}=5$. We also obtain the bounds $$m+9\le F_v(a_1,...,a_s;m-1)\le m+10,$$ if $\max \{a_1,...,a_s\}=6$. Keywords: Folkman number, Ramsey number, clique number, independence number, chromatic number

Improved Theorem 1.9 from the previous version by computing the exact value of all numbers F_v(a_1, ..., a_s; m - 1) where max{a_1, ..., a_s} = 5 (Theorem 1.8). Also some changes related to the new results are made

References in corpus (1)

• New recurrent inequality on a class of vertex Folkman numbers

Cited by in corpus (3)

• Modified vertex Folkman numbers
• Lower bounding the Folkman numbers $F_v(a_1,...,a_s;m-1)$
• New bounds on the vertex Folkman number $F_v(2,2,2,3;4)$