Summary: For a graph \(G\) and integers \(a_i \geq 1\), the expression \(G \rightarrow (a_1, \ldots, a_r)^v\) means that for any \(r\)-coloring of the vertices of \(G\) there exists a monochromatic \(a_i\)-clique in \(G\) for some color \(i \in \{1,\ldots, r\}\). The vertex Folkman numbers are defined as \(F_v (a_1 ,\ldots, a_r; H) = \min \{ |V(G)| : G\) is \(H\)-free and \(G \rightarrow (a_1, \ldots, a_r)^v\}\), where \(H\) is a graph. Such vertex Folkman numbers have been extensively studied for \(H=K_s\) with \(s>\max \{ a_i\}_{1\leq i \leq r}\). If \(a_i =a\) for all \(i\), then we use notation \(F_v (a^r; H)=F_v (a_1, \ldots, a_r; H)\).
Let \(J_k\) be the complete graph \(K_k\) missing one edge, i.e. \(J_k =K_k -e\). In this work we focus on vertex Folkman numbers with \(H=J_k\), in particular for \(k=4\) and \(a_i \leq 3\). A result by J. Nešetřil and V. Rödl [J. Comb. Theory, Ser. B 20, 243–249 (1976; Zbl 0329.05115)] implies that \(F_v (3^r; J_4)\) is well defined for any \(r\geq 2\). We present a new and more direct proof of this fact. The simplest but already intriguing case is that of \(F_v (3,3;J_4)\), for which we establish the upper bound of 135 by using the \(J_4\)-free process. We obtain the exact values and bounds for a few other small cases of \(F_v (a_1, \ldots, a_r; J_4)\) when \(a_i \leq 3\) for all \(1 \leq i \leq r\), including \(F_v (2,3;J_4)=14, F_v (2^4; J_4)=15\), and \(22 \leq F_v (2^5; J_4) \leq 25\). Note that \(F_v (2^r; J_4)\) is the smallest number of vertices in any \(J_4\)-free graph with chromatic number \(r+1\). Most of the results were obtained with the help of computations, but some of the upper bound graphs we found are interesting by themselves.