New upper bounds for vertex Folkman numbers Fu(3, k; k + 1)

Abstract

For a graph G, the symbol G → (a₁,a₂,⋯, a_r)^u means that in every r-coloring of V(G), there exists a monochromatic a_i-clique of color i for some i ∈ {1,2, ⋯,r}. The vertex Folkman number is defined as F_u(a ₁,a₂,⋯,a_r;k) = min{|V(G)| : G → (a₁,a₂,⋯ ,a_r)^u &K _k⊈ G}. In this note, with the help of computer search, 4 vertex Folkman graphs are found and new upper bounds for vertex Folkman numbers F _u(3, k; k + 1) are given.