On Some Generalized Vertex Folkman Numbers.

For a graph G and integers a i ≥ 1 , the expression G → (a 1 , ... , 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 ∈ { 1 , ... , r } . The vertex Folkman numbers are defined as F v (a 1 , ... , a r ; H) = min { | V (G) | : G is H-free and G → (a 1 , ... , 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 ≤ i ≤ r . If a i = a for all i, then we use notation F v (a r ; H) = F v (a 1 , ... , 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 ≤ 3 . A result by Nešetřil and Rödl from 1976 implies that F v (3 r ; J 4) is well defined for any r ≥ 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 , ... , a r ; J 4) when a i ≤ 3 for all 1 ≤ i ≤ r , including F v (2 , 3 ; J 4) = 14 , F v (2 4 ; J 4) = 15 , and 22 ≤ F v (2 5 ; J 4) ≤ 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. [ABSTRACT FROM AUTHOR]