On Some Generalized Vertex Folkman Numbers

Zohair Raza Hassan, Yu Jiang, David E. Narváez, Stanisław Radziszowski, Xiaodong Xu

For a graph \(G\) and integers \(a_i\ge 2\), the expression \(G \rightarrow (a_1,\dots,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,\cdots,r\}\). The vertex Folkman numbers are defined as \(F_v(a_1,\dots,a_r;H) = \min\{|V(G)| : G\) is \(H\)-free and \(G \rightarrow (a_1,\dots,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\le i \le r}\). If \(a_i=a\) for all \(i\), then we use notation \(F_v(a^r;H)=F_v(a_1,\dots,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\le 3\). We prove that \(F_v(3^r;J_4)\) is well defined for any \(r\ge 2\). The simplest but already intriguing case is that of \(F_v(3,3;J_4)\), for which we establish the upper bound of 135. We obtain the exact values and bounds for a few other small cases of \(F_v(a_1,\dots,a_r;J_4)\) when \(a_i \le 3\) for all \(1 \le i \le r\), including \(F_v(2,3;J_4)=14\), \(F_v(2^4;J_4)=15\), and \(22 \le F_v(2^5;J_4) \le 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\).

This page hosts the data related to our paper on generalized vertex Folkman numbers. All the graphs are listed in the g6 graph format.

Here you can also download the implementation of algorithm A.