New upper bound for a class of vertex Folkman numbers (Q815208)

Summary: Let \(a_1, \dots, a_r\) be positive integers, \(m=\sum_{i=1}^r (a_i-1)+1\) and \(p= \max \{a_1, \dots, a_r\}\). For a graph \(G\) the symbol \(G\rightarrow \{a_1, \dots, a_r\}\) denotes that in every \(r\)-coloring of the vertices of \(G\) there exists a monochromatic \(a_i\)-clique of color \(i\) for some \(i=1, \dots, r\). The vertex Folkman numbers \(F(a_1, \dots,a_r;m-1)=\min \{| V(G) | : G\rightarrow \{a_1, \dots, a_r\}\) and \(K_{m-1} \not \subseteq G \}\) are considered. We prove that \(F(a_1,\dots, a_r; m-1) \leq m+3p\), \(p \geq 3\). This inequality improves the bound for the numbers obtained by \textit{T. Łuczak, A. Rucińsky} and \textit{S. Urbansky} [Discrete Math. 236, 245--262 (2001; Zbl 0995.05102)].