Search

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]

For an undirected simple graph G, we write G→(H1,H2)v if and only if for everyred-blue coloring of its vertices there exists a red H1 or a blue H2. Thegeneralized vertex Folkman number Fv(H1,H2;H) is defined as the smallest integer n for which there exists an H-free graph G of order n such that G→(H1,H2)v. The generalized edge Folkman numbers Fe(H1,H2;H) are defined similarly, when colorings of the edges are considered. We show that Fe(Kk+1,Kk+1;Kk+2-e) and Fv(Kk,Kk;Kk+1-e) are well defined for k≥3. We prove the nonexistence of Fe(K3,K3;H) for some H, in particular for H=B3, where Bk is the book graph of k triangular pages, and for H=K1+P4. We pose three problems ongeneralized Folkman numbers, including the existence question of edge Folkmannumbers Fe(K3,K3;B4), Fe(K3,K3;K1+C4) and Fe(K3,K3;P2∪P3¯). Our results lead to some general inequalities involving two-color and multicolor Folkmannumbers. [ABSTRACT FROM AUTHOR]