Search

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]