On the lower bound for Fv(k, k;k + 1) and Fe(3,4;5)

Abstract

For a graph G, the symbol G → (a₁,a₂) _v (resp. G → (a₁,a₂)^e) means that in every 2-coloring of V(G) (resp. E(G)), there exists a monochromatic a_i-clique of color i for some i ε {1,2}. The 2-color vertex (resp. edge) Folkman number is defined as F_v(a₁,a ₂;k) = min{|V(G)| : G → (a₁,a₂) _v Λ K_k G}, (resp. F_e(a ₁,a₂;k) = min{|V(G)| : G → (a₁,a ₂)^e A K_k G}. ) In this note, we show that F_e(3,k;k + 1) > F_v(k,k;k + 1) > 4k - 1. In addition, we obtain that F_e(3,4;5) ≥ 22.