Chromatic Vertex Folkman Numbers

For graph $G$ and integers $a_1\ge \cdots \ge a_r\ge 2$, we write $G \rightarrow (a_1 ,\cdots ,a_r)^v$ifandonlyifforevery$r$-coloring of the vertex set $V(G)$ there exists a monochromatic $K_{a_i}$ in $G$ for some color $i\in \{1,\cdots ,r\}$. The vertex Folkman number $F_v(a_1,\cdots ,a_r;s)$ is defined as the smallest integer $n$ for which there exists a $K_s$-free graph $G$ of order $n$ such that $G\to (a_1,\cdots ,a_r{)}^v$. It is well known that if $G\to (a_1,\cdots ,a_r{)}^v$ then $\chi (G)\ge m$, where $m=1+{\sum }_{i=1}^r(a_i-1)$. In this paper we study such Folkman graphs $G$ with chromatic number $\chi (G)=m$, which leads to a new concept of chromatic Folkman numbers. We prove constructively some existential results, among others that for all $r,s\ge 2$ there exist $K_{s+1}$-free graphs $G$ such that $G\to (s,{\cdots }_r,s{)}^v$ and $G$ has the smallest possible chromatic number $r(s-1)+1$ for this $r$-color arrowing to hold. We also conjecture that, in some cases, our construction is the best possible, in particular that for every $s\ge 2$ there exists a $K_{s+1}$-free graph $G$ on $F_v(s,s;s+1)$ vertices with $\chi (G)=2s-1$ such that $G\to (s,s{)}^v$.