Menu
Let G be a graph and a1,…, as be positive integers. The expression \(G\, \underrightarrow{v}(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 numbers \(F_v(a_1, …, a_s; q)\) are defined by the equality:
\[F_v(a_1, …, a_s; q) = min\{|V(G)| : G\, \underrightarrow{v}(a_1,…,a_s)\,\, and K_q \nsubseteq G\}\].
Let \(m = \sum^s_{i=1} (a_i – 1) + 1\). It is easy to see that \(F_v(a_1,…, a_s; q) = m\) if \(q \geq 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} ≤ 5\) and none of these numbers is known if \(max{a_1, …, a_s} ≥ 6\). In this paper we present computer algorithms, with the help of which we compute all Folkman numbers \(F_v (a_1, .., a_s;m – 1)\) when \(max{a_1,.., a_s} = 6\). We also prove that \(F_v (2,2,7;8) = 20\) and obtain new bounds on the numbers \(F_v(a_1, …, a_s;m – 1)\) when \(max(a_1, …, a_s) = 7\).