Chromatic vertex Folkman numbers (Q2195230)

Summary: For graph \(G\) and integers \(a_1 \geqslant \cdots \geqslant a_r \geqslant 2\), we write \(G \rightarrow (a_1 ,\cdots ,a_r)^v\) if and only if for every \(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 \rightarrow (a_1 ,\cdots ,a_r)^v\). It is well known that if \(G \rightarrow (a_1 ,\cdots ,a_r)^v\) then \(\chi(G) \geqslant 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 \geqslant 2\) there exist \(K_{s+1}\)-free graphs \(G\) such that \(G \rightarrow (s,\cdots_r,s)^v\) and \(G\) has the smallest possible chromatic number \(r(s-1)+1\) with respect to this property. Among others we conjecture that for every \(s \geqslant 2\) there exists a \(K_{s+1}\)-free graph \(G\) on \(F_v(s,s;s+1)\) vertices with \(\chi(G)=2s-1\) and \(G\rightarrow (s,s)^v\).